[Link] https://www.acmicpc.net/problem/13460
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
int n, m, maxv;
const int INF = 987654321;
int gi, gj, ans = INF;
bool bmap[20][20];
int di[4] = { 0, -1, 0, 1 };
int dj[4] = { -1, 0, 1, 0 };
void dfs(int cnt, int ri, int rj, int bi, int bj) {
if(cnt > 10) return;
if(ri == gi && rj == gj && (bi != gi || bj != gj)) {
ans = min(ans, cnt);
return;
}
for(int i = 0; i < 4; i++) {
bool rstop = false, bstop = false, rgoal = false, bgoal = false;
int sri = ri, srj = rj, sbi = bi, sbj = bj;
while(true) {
if(sri == gi && srj == gj) sri = -1, srj = -1, rgoal = true;
if(sbi == gi && sbj == gj) sbi = -1, sbj = -1, bgoal = true;
if(!rstop) if(sri + di[i] < 0 || srj + dj[i] < 0 || sri + di[i] >= n || srj + dj[i] >= m || !bmap[sri+di[i]][srj+dj[i]]) rstop = true;
if(!bstop) if(sbi + di[i] < 0 || sbj + dj[i] < 0 || sbi + di[i] >= n || sbj + dj[i] >= m || !bmap[sbi+di[i]][sbj+dj[i]]) bstop = true;
if(rstop && bstop) break;
else if(!rstop && !bstop) sbi+=di[i], sbj+=dj[i], sri+=di[i], srj+=dj[i];
else if(rstop) {
if(sbi+di[i] == sri && sbj+dj[i] == srj) break;
sbi+=di[i], sbj+=dj[i];
}
else {
if(sri+di[i] == sbi && srj+dj[i] == sbj) break;
sri+=di[i], srj+=dj[i];
}
}
if(bgoal) continue;
if(rgoal) {
if(cnt + 1 > 10) continue;
ans = min(ans, cnt + 1);
return;
}
if(sri == ri && srj == rj && sbi == bi && sbj == bj) continue;
dfs(cnt+1, sri, srj, sbi, sbj);
}
}
int main() {
cin >> n >> m;
int ri, rj, bi, bj;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
char c; cin >> c;
if(c == '#') continue;
bmap[i][j] = true;
if(c == 'O') gi = i, gj = j;
else if(c == 'R') ri = i, rj = j;
else if(c == 'B') bi = i, bj = j;
}
}
dfs(0, ri, rj , bi, bj);
cout << (ans == INF ? -1 : ans);
return 0;
}