[백준 13460] 구슬 탈출2

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

13460번: 구슬 탈출 2

 

요구사항

1. 최소한의 숫자로 빨간 구슬 탈출 시키기

 

풀이

1. 빨간 구슬 이동

2. 파란 구슬 이동

3. 구슬이 겹칠 경우 처리

4. 구멍에 빠졋는지 확인

5. 현재 도착지에 이전에 도착했는지 확인

 

정답 출력 조건........ㅠ

 

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

using namespace std;

struct go {
	int x;
	int y;
	int cnt;
};
char map[12][12];
int visit[12][12][12][12];
int n, m;
int rs, rc, br, bc;
int ans = 987654321;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };

void solve() {
	go nr;
	go nb;
	int cnt = 0;
	queue<pair<go, go>> q;
	q.push({ {rs,rc,0},{br,bc,0} });
	visit[rs][rc][br][bc] = 1;
	while (!q.empty()) {
		nr.x = q.front().first.x;
		nr.y = q.front().first.y;
		nb.x = q.front().second.x;
		nb.y = q.front().second.y;
		cnt = q.front().first.cnt;
		if (cnt >= 10)
			return;
		//cout << "nowred " << nr.x << " " << nr.y << " nowblue" << " " << nb.x << " " << nb.y << endl;
		q.pop();
		for (int i = 0; i < 4; i++) {
			//빨강부터
			int nowredr = nr.x;
			int nowredc = nr.y;
			int nowbluer = nb.x;
			int nowbluec = nb.y;
			int blueflag = 0;
			int redflag = 0;
			//빨강 이동
			while (true) {
				nowredr += dr[i];
				nowredc += dc[i];
				if (map[nowredr][nowredc] == '#')
				{
					nowredr -= dr[i];
					nowredc -= dc[i];
					break;
				}
				else if (map[nowredr][nowredc] == 'O')
				{
					redflag = 1; break;
				}
			}
			//파랑 이동
			while (true) {
				nowbluer += dr[i];
				nowbluec += dc[i];
				if (map[nowbluer][nowbluec] == '#')
				{
					nowbluer -= dr[i];
					nowbluec -= dc[i];
					break;
				}
				else if (map[nowbluer][nowbluec] == 'O')
				{
					blueflag = 1;
					break;
				}
			}
			if (redflag == 1 && blueflag == 0) {
				ans = min(ans, cnt + 1);
				return;
			}
			else if (redflag == 1 && blueflag == 1) {
				continue;
			}
			else if (redflag == 0 && blueflag == 1) {
				continue;
			}
			else if (redflag == 0 && blueflag == 0) {
				if (nowredr == nowbluer && nowredc == nowbluec) {
					if (i == 0) {
						if (nr.x < nb.x) 
							nowbluer++;
						else 
							nowredr++;
					}
					else if (i == 1) {
						if (nr.y < nb.y) 
							nowbluec++;
						else 
							nowredc++;
					}
					else if (i == 2) {
						if (nr.x < nb.x) 
							nowredr--;
						else {
							nowbluer--;
						}
					}
					else if (i == 3) {
						if (nr.y < nb.y) 
							nowredc--;
						else 
							nowbluec--;
					}
				}
			}
			if(visit[nowredr][nowredc][nowbluer][nowbluec]==1) {
				continue;
			}
			visit[nowredr][nowredc][nowbluer][nowbluec] = 1;
			q.push({ {nowredr,nowredc,cnt+1},{nowbluer,nowbluec} });
		}
	}
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	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] == 'R') {
				rs = i;
				rc = j;
				map[i][j] = '.';
			}
			else if (map[i][j] == 'B') {
				br = i;
				bc = j;
				map[i][j] = '.';
			}
		}
	}
	solve();
	if (ans == 987654321) {
		cout << "-1" << endl;
	}
	else
		cout << ans << endl;
}