13460번:구슬 탈출 2

https://www.acmicpc.net/problem/13460

 

메모리:1140KB

시간:0ms

코드길이:2620B

#include <stdio.h>

struct cBead { int xy[4], cnt = 0; };

bool visit[11][11][11][11];
char map[11][11];
char mapCopy[11][11];
cBead que[121 * 4];
int N, M, head, tail;
int arrBead[2];
int xyNew[4];
int r, c;
bool isFinish[2] = { 0, 0 };


bool process(int r, int c, int bead, int rOffSet, int cOffSet )
{
	if (map[r][c] == '#' || map[r][c] == 'T') {
		xyNew[arrBead[bead]] = r + rOffSet;
		xyNew[arrBead[bead] + 1] = c + cOffSet;
		map[r + rOffSet][c + cOffSet] = 'T';
		return true;
	}
	else if (map[r][c] == 'O') {
		isFinish[arrBead[bead] / 2] = true;
		return true;
	}

	return false;
}


int move(int dir)
{
	isFinish[0] = isFinish[1] = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = mapCopy[i][j];
		}
	}

	if ((dir == 1 && que[head].xy[0] <= que[head].xy[2])
		|| (dir == 2 && que[head].xy[0] >= que[head].xy[2])
		|| (dir == 3 && que[head].xy[1] <= que[head].xy[3])
		|| (dir == 4 && que[head].xy[1] >= que[head].xy[3]))	
	{
		arrBead[0] = 0; arrBead[1] = 2;
	}
	else 
	{
		arrBead[0] = 2;	arrBead[1] = 0;
	}

	for (int bead = 0; bead < 2; bead++)
	{
		r = que[head].xy[arrBead[bead]];
		c = que[head].xy[arrBead[bead] + 1];
		
		if (dir == 1) { for (; r >= 0; r--) { if (process(r, c, bead, 1, 0)) { break; } } }
		else if (dir == 2) { for (; r < N; r++) { if (process(r, c, bead, -1, 0)) { break; } } }
		else if (dir == 3) { for (; c >= 0; c--) { if (process(r, c, bead, 0, 1)) { break; } } }
		else if (dir == 4) { for (; c < M; c++) { if (process(r, c, bead, 0, -1)) { break; } } }
	}

	if (isFinish[1]) { return 0; }
	else if (isFinish[0] && !isFinish[1]) 
	{
		if (que[head].cnt + 1 > 10) { return -1; }
		else { return que[head].cnt + 1; }
	}
	
	if (visit[xyNew[0]][xyNew[1]][xyNew[2]][xyNew[3]] == 1) { return 0; }
	visit[xyNew[0]][xyNew[1]][xyNew[2]][xyNew[3]] = 1;

	tail++;
	que[tail].cnt = que[head].cnt + 1;
	for (int i = 0; i < 4; i++) { que[tail].xy[i] = xyNew[i]; }

	return 0;
}

int main()
{
	head = 0, tail = 0;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) { scanf("%s", &mapCopy[i]); }

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (mapCopy[r][c] == 'R') {
				mapCopy[r][c] = '.';
                que[0].xy[0] = r;
				que[0].xy[1] = c;
			}
			else if (mapCopy[r][c] == 'B') {
				mapCopy[r][c] = '.';
                que[0].xy[2] = r;
				que[0].xy[3] = c;
			}
		}
	}
	
	visit[que[head].xy[0]][que[head].xy[1]][que[head].xy[2]][que[head].xy[3]] = 1;
	int ret;
	while (head <= tail) {
		for (int i = 1; i <= 4; i++) {
			ret = move(i);
			if (ret != 0) {
				printf("%d", ret); 
				return 0;
			}
		}
		head++;
	}
	printf("-1");
	return 0;
}