백준 소스코드 [C++] 15644 구슬 탈출 3

www.acmicpc.net/problem/15644

15644번: 구슬 탈출 3

백준 소스코드 [C++] 15644 구슬 탈출 3

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, m;
char arr[10][10];
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1, 0, -1, 0 };
string ds = "DRUL";
int holey, holex;

struct dot {
	int redy, redx, bluey, bluex;
	string s;
};
dot info;

void bfs() {
	queue<dot> q, t;
	q.push(info);
	int cnt = 0;
	while (q.empty() != true) {

		while (q.empty() != true) {
			t.push(q.front());
			q.pop();
		}

		cnt++;
		if (cnt > 10) {
			cout << "-1";
			return;
		}

		while (t.empty() != true) {
			dot olddot = t.front();
			t.pop();

			for (int i = 0;i < 4;i++) {
				dot newdot = olddot;
				int redcnt = 0, bluecnt = 0;
				newdot.s += ds[i];
				while (true) {
					if (arr[newdot.redy + dy[i]][newdot.redx + dx[i]] != '#') {
						newdot.redy += dy[i]; newdot.redx += dx[i];
						redcnt++;
					}
					else break;
					if (newdot.redy == holey && newdot.redx == holex) break;
				}

				while (true) {
					if (arr[newdot.bluey + dy[i]][newdot.bluex + dx[i]] != '#') {
						newdot.bluey += dy[i]; newdot.bluex += dx[i];
						bluecnt++;
					}
					else break;
					if (newdot.bluey == holey && newdot.bluex == holex) break;
				}

				if (newdot.bluey == holey && newdot.bluex == holex)continue;
				else if (newdot.redy == holey && newdot.redx == holex) {
					cout << cnt<<'\n'<<newdot.s;
					return;
				}

				else if (newdot.bluey == newdot.redy && newdot.bluex == newdot.redx) {
					if (redcnt < bluecnt) {
						newdot.bluey -= dy[i];
						newdot.bluex -= dx[i];

						if (!(newdot.bluey == olddot.bluey &&
							newdot.bluex == olddot.bluex &&
							newdot.redy == olddot.redy &&
							newdot.redx == olddot.redx))
							q.push(newdot);


					}
					else {
						newdot.redy -= dy[i];
						newdot.redx -= dx[i];

						if (!(newdot.bluey == olddot.bluey &&
							newdot.bluex == olddot.bluex &&
							newdot.redy == olddot.redy &&
							newdot.redx == olddot.redx))
							q.push(newdot);

					}
				}
				else {
					if (!(newdot.bluey == olddot.bluey &&
						newdot.bluex == olddot.bluex &&
						newdot.redy == olddot.redy &&
						newdot.redx == olddot.redx))
						q.push(newdot);
				}

			}
		}
	}
	cout << "-1";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;

	for (int i = 0;i < n;i++)
		for (int j = 0;j < m;j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') { info.redy = i; info.redx = j; }
			if (arr[i][j] == 'B') { info.bluey = i; info.bluex = j; }
			if (arr[i][j] == 'O') { holey = i; holex = j; }
		}
	info.s = "";
	bfs();
	return 0;
}