#include <bits/stdc++.h> using namespace std;
#define endl '\n'
char board[11][11]; bool check[11][11][11][11];
int dy[4] = {0, 0, -1, 1}; int dx[4] = {-1, 1, 0, 0};
pair<int, int> moveBall(pair<int, int> ball, int dir) { while (board[ball.first + dy[dir]][ball.second + dx[dir]] != '#') { if (board[ball.first][ball.second] == 'O') { break; }
ball.first += dy[dir]; ball.second += dx[dir]; }
return ball; }
bool isBlueExit(pair<int, int> next_blue) { if (board[next_blue.first][next_blue.second] == 'O') { return true; } return false; }
bool isRedExit(pair<int, int> next_red) { if (board[next_red.first][next_red.second] == 'O') { return true; } return false; }
bool isSame(pair<int, int> next_red, pair<int, int> next_blue) { if (next_red.first == next_blue.first && next_red.second == next_blue.second) { return true; } return false; }
void moveBack(pair<int, int> cnt_red, pair<int, int> cnt_blue, pair<int, int>& next_red, pair<int, int>& next_blue, int dir) { if (dir == 0) { if (cnt_red.second < cnt_blue.second) { next_blue.second++; } else { next_red.second++; } }
if (dir == 1) { if (cnt_red.second > cnt_blue.second) { next_blue.second--; } else { next_red.second--; } }
if (dir == 2) { if (cnt_red.first < cnt_blue.first) { next_blue.first++; } else { next_red.first++; } }
if (dir == 3) { if (cnt_red.first > cnt_blue.first) { next_blue.first--; } else { next_red.first--; } } }
int bfs(pair<int, int> redBall, pair<int, int> blueBall, pair<int, int> exit) { queue<pair<pair<int, int>, pair<int, int>>> q; q.push({redBall, blueBall}); check[redBall.first][redBall.second][blueBall.first][blueBall.second] = true;
int count = 0; while (!q.empty()) { count++; int q_size = q.size();
if (count > 10) { break; }
while (q_size--) { pair<int, int> cnt_red = q.front().first; pair<int, int> cnt_blue = q.front().second; q.pop();
for (int i = 0; i < 4; i++) { pair<int, int> next_red = moveBall(cnt_red, i); pair<int, int> next_blue = moveBall(cnt_blue, i);
if (isBlueExit(next_blue)) { continue; }
if (isRedExit(next_red)) { return count; }
if (isSame(next_red, next_blue)) { moveBack(cnt_red, cnt_blue, next_red, next_blue, i); }
if (check[next_red.first][next_red.second][next_blue.first][next_blue.second] == false) { q.push({next_red, next_blue}); check[next_red.first][next_red.second][next_blue.first][next_blue.second] = true; } } } }
return -1; }
int main(void) { int row, col; cin >> row >> col;
pair<int, int> redBall; pair<int, int> blueBall; pair<int, int> exit;
for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cin >> board[i][j];
if (board[i][j] == 'R') { redBall = {i, j}; board[i][j] = '.'; }
if (board[i][j] == 'B') { blueBall = {i, j}; board[i][j] = '.'; }
if (board[i][j] == 'O') { exit = {i, j}; } } }
cout << bfs(redBall, blueBall, exit) << endl;
return 0; }
|