백준 : 13460*

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

13460번: 구슬 탈출 2

 

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int N, M;
char map[11][11];

int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

int R_x, R_y, B_x, B_y;
struct Q {
	int R_x;
	int R_y;
	int B_x;
	int B_y;
	int current;
};

int BFS() {
	queue<Q> q;

	q.push({ R_x,R_y,B_x,B_y,0 });
	int tmp_y, tmp_x;
	while (!q.empty()) {
		Q buffer = q.front();
		//cout << "현위치\n";
		//cout << buffer.R_x << " " << buffer.R_y << " " << buffer.B_x << " " << buffer.B_y << " " << buffer.current<< endl;
		q.pop();
		if (buffer.current >= 10) return -1;
		for (int d = 0; d < 4; ++d) {
			//이동시키기
			R_x = buffer.R_x;
			R_y = buffer.R_y;
			B_x = buffer.B_x;
			B_y = buffer.B_y;

			//R 이동
			while (true) {
				tmp_y = R_y + dy[d];
				tmp_x = R_x + dx[d];
				if (map[tmp_y][tmp_x] == '#') break;
				else if (map[tmp_y][tmp_x] == 'O') {
					R_y = tmp_y;
					R_x = tmp_x;
					break;
				}
				R_y = tmp_y;
				R_x = tmp_x;
			}

			//B 이동
			while (true) {
				tmp_y = B_y + dy[d];
				tmp_x = B_x + dx[d];
				if (map[tmp_y][tmp_x] == '#') break;
				else if (map[tmp_y][tmp_x] == 'O') {
					B_y = tmp_y;
					B_x = tmp_x;
					break;
				}
				B_y = tmp_y;
				B_x = tmp_x;
			}

			//서로의 위치가같으면 처리하기

			//같을 경우
			if (R_x == B_x && R_y == B_y) {
				if (map[R_y][R_x] == 'O') {
					continue;
				}

				if (d == 0) {
					//오른
					if (buffer.R_x > buffer.B_x) {
						B_x -= dx[d];
					}
					else {
						R_x -= dx[d];
					}
				}
				else if (d == 1) {
					//왼
					if (buffer.R_x < buffer.B_x) {
						B_x -= dx[d];
					}
					else {
						R_x -= dx[d];
					}
				}
				else if (d == 2) {
					//위
					if (buffer.R_y < buffer.B_y) {
						B_y -= dy[d];
					}else {
						R_y -= dy[d];
					}
				}
				else if (d == 3) {
					//아래
					if (buffer.R_y > buffer.B_y) {
						B_y -= dy[d];
					}
					else {
						R_y -= dy[d];
					}

				}

			}
			//다를 경우
			else {
				if (map[B_y][B_x] == 'O') continue;

				if (map[R_y][R_x] == 'O') return buffer.current + 1;

			}

			//R 와 B의 위치가 변하지 안을경우
			if (buffer.B_x == B_x && buffer.B_y == B_y && buffer.R_x == R_x && buffer.R_y == R_y) {
				continue;
			}
			//cout << R_x <<" "<<R_y<<" "<<B_x<<" "<<B_y<<endl;
			q.push({R_x,R_y,B_x,B_y,buffer.current + 1});
		}
	}
	return -1;
}

int main(void) {
	cin >> N >> M;

	

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 'B') {
				B_y = i; B_x = j;
			}
			else if (map[i][j] == 'R') {
				R_y = i; R_x = j;
			}
		}
	}

	map[R_y][R_x] = '.';
	map[B_y][B_x] = '.';
	cout << BFS();
	return 0;
}