구술탈출 2

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

13460번: 구슬 탈출 2

#include <iostream>
#include <queue>

using namespace std;

int n, m;
char g[11][11];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int c[11][11][11][11] = { 0 }; // 지나갔는지 확인
int rx, ry, bx, by,d;
struct bead {
	int rx, ry, bx, by, d; //좌표 및 움직이는 횟수 저장
};
queue<bead> Q;

void Move(int &x, int &y, int &d, int dx, int dy) {
	while (g[x + dx][y + dy] != '#' && g[x][y] != 'O') {
		x += dx; y += dy; d++;
	}
}

void BFS() {
	while (!Q.empty()) {
		rx = Q.front().rx;
		ry = Q.front().ry;
		bx = Q.front().bx;
		by = Q.front().by;
		d = Q.front().d;
		Q.pop();
		if (d >= 10) break;
		for (int i = 0; i < 4; i++) {
			int nrx = rx; int nry = ry;
			int nbx = bx; int nby = by;
			int rc = 0; int bc = 0;
			Move(nrx, nry, rc, dx[i], dy[i]);
			Move(nbx, nby, bc, dx[i], dy[i]);
			if (g[nbx][nby] == 'O') continue; //B가 들어갔는지 확인
			if (g[nrx][nry] == 'O') {
				cout << d + 1 << "\n";
				return;
			}
			if (nrx == nbx && nry == nby) { //R과 B가 겹쳤을때 상황
				if (rc > bc) {
					nrx -= dx[i]; nry -= dy[i];
				}
				else {
					nbx -= dx[i]; nby -= dy[i];
				}
			}
			if (c[nrx][nry][nbx][nby]) continue;
			c[nrx][nry][nbx][nby] = 1;
			Q.push({ nrx,nry,nbx,nby,d + 1 });
		}
	}
	cout << "-1" << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	int i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> g[i][j];
			if (g[i][j] == 'R') {
				rx = i; ry = j;
			}
			else if (g[i][j] == 'B') {
				bx = i; by = j;
			}
		}
	}
	Q.push({ rx,ry,bx,by,0 });
	c[rx][ry][bx][by] = 1;
	BFS();
	return 0;
}