/*
* Problem :: 13460 / 구슬 탈출 2
*
* Kind :: BFS
*
* Insight
* - 전체 가능한 경우의 수는 4^10번 이 아닌 2^10번 이다
* + 방금 전 기울인 쪽으로 보드를 다시 기울이는 것은 아무 의미가 없다
* + 방금 전 기울인 쪽의 반대 방향으로 보드를 기울이는 것은 아무 의미가 없다
*
* Point
* - 각각의 구슬이 한 칸씩 이동할 때마다, 구멍에 빠졌는지 그렇지 않은지 확인해주어야 한다
* # 한칸 한칸 움직일 때마다 구슬을 추적해야 한다
*
* - 보드를 기울인 후, 구슬의 상태에 따라 추후 게임의 진행여부가 결정된다
* # 편의상 보드를 기울이는 것을 구현한 함수에서 상태를 표시하는 값을 같이 반환하여 구현했다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, M;
char board[10][10];
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
struct Point { int y, x; };
struct Status { int pd; Point R, B; };
Point O;
#define SUCCESS 1
#define CONTINUE 0
#define FAIL -1
// Set up : Functions Declaration
bool operator == (const Point &u, const Point &v);
pair<int,Status> tilt(Status C, int dir);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
Point SR{}, SB{}; /* 빨간 구슬 시작위치, 파란 구슬 시작위치 */
cin >> N >> M;
for (int i=0; i<N; i++) {
string line; cin >> line;
for (int j=0; j<M; j++) {
board[i][j] = line.at(j);
if (board[i][j] != '#') {
if (board[i][j] == 'R') {
SR.y = i; SR.x = j;
}
if (board[i][j] == 'B') {
SB.y = i; SB.x = j;
}
if (board[i][j] == 'O') {
O.y = i; O.x = j;
}
board[i][j] = '.'; /* board 에는 '.' 과 '#' 만 남게됨 */
}
}
}
// Process
queue<Status> que;
/* 게임 중간의 상태는 이전에 보드를 기울였던 방향과 각 구슬의 위치로 나타낼 수 있음 */
que.push({-1, SR, SB}); /* 초기 상태를 Queue 에 넣어줌 */
int cnt = 0; /* 보드를 기울인 횟수 */
while (not(que.empty())) {
int size = que.size();
cnt++;
if (cnt > 10) break; /* 10번 넘게 보드를 기울이는 경우는 고려하지 않음 */
while (size--) {
Status C = que.front(); /* 현재 다루고 있는 게임 중간 상태 */
int pd = C.pd; /* previous direction */
que.pop();
for (int i=0; i<4; i++) {
/* 이전에 기울였던 방향, 또는 그 반대 방향이면 그냥 넘어감 */
if (pd == i || 3-pd == i) continue;
int code; Status A{};
/* 보드를 i 방향으로 기울여서
* 게임의 결과를 나타내는 code 와 상태를 나타내는 Status 를 받음 */
tie(code, A) = tilt(C, i);
// Control : Output
/* 성공 */
if (code == SUCCESS) {
cout << cnt << endl;
exit(0);
}
/* 게임 계속 */
else if (code == CONTINUE) {
que.push(A);
}
/* 실패는 그대로 게임종료 */
}
}
}
// Control : Output
cout << -1 << endl;
}
// Helper Functions
bool operator == (const Point &u, const Point &v)
/* 좌표 비교를 편하게 하기 위해서 연산자 오버로딩을 함 */
{
return make_tuple(u.x, u.y) == make_tuple(v.x, v.y);
}
pair<int,Status> tilt(Status C, int dir)
/* 보드를 dir 방향으로 기울인 후, 게임의 결과를 나타내는 (int)code 와 게임의 상태를 반환함 */
{
Point CR = C.R; /* 현재 빨간 구슬의 위치 */
Point CB = C.B; /* 현재 파란 구슬의 위치 */
bool isRMoved, isBMoved;
bool isRFallen = false, isBFallen = false;
do {
isRMoved = false;
isBMoved = false;
if (not(isRFallen)) { /* 현재 빨간 구슬이 떨어지지 않았다면 */
int nry = CR.y + dy[dir]; /* new R y */
int nrx = CR.x + dx[dir]; /* new R x */
Point NR{nry, nrx};
/* 다음 빨간 구슬의 위치가 장애물이 아니고 */
if (board[nry][nrx] != '#') {
/* 구멍이거나 현재 파란구슬이 있는 위치가 아니라면 */
if (NR == O || not(NR == CB)) {
/* 움직인다 */
isRMoved = true;
/* 빨간 구슬의 위치 갱신 */
CR = NR;
}
}
}
if (not(isBFallen)) { /* 현재 파란 구슬이 떨어지지 않았다면 */
int nby = CB.y + dy[dir]; /* new B y */
int nbx = CB.x + dx[dir]; /* new B x */
Point NB{nby, nbx};
/* 당음 파란 구슬의 위치가 장애물이 아니고 */
if (board[nby][nbx] != '#') {
/* 구멍이거나 현재 파란구슬이 있는 위치가 아니라면 */
if (NB == O || not(NB == CR)) {
/* 움직인다 */
isBMoved = true;
/* 파란 구슬의 위치 갱신 */
CB = NB;
}
}
}
/* 각각의 구슬이 떨어졌는지 확인 */
isRFallen = (CR == O);
isBFallen = (CB == O);
} while (isRMoved || isBMoved); /* 두 구슬이 모두 움직이지 않을 때까지 반복 */
/* 파란 구슬이 떨어졌으면 */
if (isBFallen) {
/* 실패 */
return {FAIL, {dir, CR, CB}};
/* 파란 구슬은 안 떨어졌는데 */
/* 빨간 구슬이 떨어졌으면 */
} else if (isRFallen) {
/* 성공 */
return {SUCCESS, {dir, CR, CB}};
/* 빨간 구슬도 안 떨어졌으면 */
} else {
/* 게임 계속 */
return {CONTINUE, {dir, CR, CB}};
}
}