간단한 bfs 이지만 경우의 수가 매우 많은 귀찮은(?) 문제였다. 일단 시간제한은 2초 이지만 보드의 가로 세로가 최대 10 이므로 어떻게든 지지고 볶아도 시간 초과는 나지 않는 문제였다.
때문에 구현에만 정성을 쏟으면 된다. 로직은 다음과 같다.
- 위, 아래, 오른쪽, 왼쪽 4가지로 구분한다.
- 각 4가지별로 빨강이 앞에 있는 경우, 뒤에 있는 경우로 나눈다.
- 나눈 경우에 따라 while 문으로 벽이 나올 때까지 빨간 공과 파란 공을 움직인다. (이 때 서로 앞지르지는 못한다)
위의 1→2→3 을 반복하면 간단하게 문제가 풀린다. 이 때 시간 복잡도는 이전에 위로 움직인 경우 다음에 위로 움직이지 않게끔 하여 최대 3^10 정도가 나오게 된다. 대략 6만 정도가 나오게 되고, 각 케이스마다 1000줄씩 있다고 가정해도 6천만 정도의 넉넉한 복잡도가 나오게 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>
#define RED 2
#define BLUE 3
#define UP 100
#define DOWN 101
#define LEFT 102
#define RIGHT 103
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int n, m;
int check[12][12];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int dir[] = { UP, DOWN, LEFT, RIGHT };
int _min = 100;
void dfs(int _cnt, int _dir, pii _red, pii _blue) {
if (_cnt > 10) return;
if (_dir == UP) {
if (_red.first < _blue.first) {
// red 가 더 위에 있는 경우
bool checkout = false;
while (1) {
if (check[_red.first - 1][_red.second] == -1) break;
else if (check[_red.first - 1][_red.second] == 1) {
checkout = true;
break;
}
else {
_red.first -= 1;
}
}
while (1) {
if (!checkout && _blue.first - 1 == _red.first && _blue.second == _red.second) break;
else if (check[_blue.first - 1][_blue.second] == -1) break;
else if (check[_blue.first - 1][_blue.second] == 1) {
return;
}
else {
_blue.first -= 1;
}
}
if(checkout ) _min = min(_min, _cnt);
}
else {
// blue 가 더 위에 있는 경우
while (1) {
if (check[_blue.first - 1][_blue.second] == -1) break;
else if (check[_blue.first - 1][_blue.second] == 1) {
return;
}
else {
_blue.first -= 1;
}
}
while (1) {
if (_blue.first + 1 == _red.first && _blue.second == _red.second) break;
if (check[_red.first - 1][_red.second] == -1) break;
else if (check[_red.first - 1][_red.second] == 1) {
_min = min(_min, _cnt);
return;
}
else {
_red.first -= 1;
}
}
}
}
else if (_dir == DOWN) {
if (_red.first < _blue.first) {
// red 가 더 위에 잇는 경우
while (1) {
if (check[_blue.first + 1][_blue.second] == -1) break;
else if (check[_blue.first + 1][_blue.second] == 1) {
return;
}
else {
_blue.first += 1;
}
}
while (1) {
if (_red.first + 1 == _blue.first && _blue.second == _red.second) break;
else if (check[_red.first + 1][_red.second] == -1) break;
else if (check[_red.first + 1][_red.second] == 1) {
_min = min(_min, _cnt);
return;
}
else {
_red.first += 1;
}
}
}
else {
// red가 밑에 있는 경우
bool checkout = false;
while (1) {
if (check[_red.first + 1][_red.second] == -1) break;
else if (check[_red.first + 1][_red.second] == 1) {
checkout = true;
break;
}
else _red.first += 1;
}
while (1) {
if (!checkout && _blue.first + 1 == _red.first && _blue.second == _red.second) break;
else if (check[_blue.first + 1][_blue.second] == -1) break;
else if (check[_blue.first + 1][_blue.second] == 1) {
return;
}
else _blue.first += 1;
}
if(checkout) _min = min(_min, _cnt);
}
}
else if (_dir == LEFT) {
if (_red.second > _blue.second) {
// red 가 오른쪽에 있는 경우
while (1) {
if (check[_blue.first][_blue.second - 1] == -1) break;
else if (check[_blue.first][_blue.second - 1] == 1) {
return;
}
else _blue.second -= 1;
}
while (1) {
if (_red.second - 1 == _blue.second && _blue.first == _red.first) break;
else if (check[_red.first][_red.second - 1] == -1) break;
else if (check[_red.first][_red.second - 1] == 1) {
_min = min(_min, _cnt);
return;
}
else _red.second -= 1;
}
}
else {
// red 가 왼쪽에 있는 경우
bool checkout = false;
while (1) {
if (check[_red.first][_red.second - 1] == -1) break;
else if (check[_red.first][_red.second - 1] == 1) {
checkout = true;
break;
}
else _red.second -= 1;
}
while (1) {
if (!checkout && _blue.second - 1 == _red.second && _blue.first == _red.first) break;
else if (check[_blue.first][_blue.second - 1] == -1) break;
else if (check[_blue.first][_blue.second - 1] == 1) {
return;
}
else _blue.second -= 1;
}
if(checkout) _min = min(_min, _cnt);
}
}
else if (_dir == RIGHT) {
if (_red.second > _blue.second) {
// red 가 오른쪽에 있는 경우
bool checkout = false;
while (1) {
if (check[_red.first][_red.second + 1] == -1) break;
else if (check[_red.first][_red.second + 1] == 1) {
checkout = true;
break;
}
else _red.second += 1;
}
while (1) {
if (!checkout && _blue.second + 1 == _red.second && _blue.first == _red.first) break;
else if (check[_blue.first][_blue.second + 1] == -1) break;
else if (check[_blue.first][_blue.second + 1] == 1) {
return;
}
else _blue.second += 1;
}
if(checkout )_min = min(_min, _cnt);
}
else {
// red 가 왼쪽에 있는 경우
while (1) {
if (check[_blue.first][_blue.second + 1] == -1) break;
else if (check[_blue.first][_blue.second + 1] == 1) {
return;
}
else _blue.second += 1;
}
while (1) {
if (_red.second + 1 == _blue.second && _blue.first == _red.first) break;
else if (check[_red.first][_red.second +1] == -1) break;
else if (check[_red.first][_red.second + 1] == 1) {
_min = min(_min, _cnt);
return;
}
else _red.second += 1;
}
}
}
for (int i = 0; i < 4; i++) {
if (dir[i] == _dir) continue;
dfs(_cnt + 1, dir[i], _red, _blue);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
string row;
pii red, blue;
for (int i = 1; i <= n; i++) {
cin >> row;
for (int j = 1; j <= m; j++) {
if (row.at(j-1) == '#') check[i][j] = -1;
else if (row.at(j-1) == '.') check[i][j] = 0;
else if (row.at(j-1) == 'O') check[i][j] = 1;
else if (row.at(j-1) == 'R') red = { i,j };
else if (row.at(j-1) == 'B') blue = {i,j};
}
}
// 기울이는 행동 자체를 탐색
for (int i = 0; i < 4; i++) {
dfs(1, dir[i], red, blue);
}
if (_min == 100) cout << -1;
else cout << _min;
return 0;
}
