#include #include #include #include #define sz 20003 using namespace std; int n, m; struct now { int ry; int rx; int by; int bx; int depth; bool stop; bool finish; }; char arr[10][10]; bool visited[10][10][10][10]; bool chkR(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; return (ry >= n || ry < 0 || rx >= m || rx < 0 || arr[ry][rx] == '#'); } bool chkB(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; return (by >= n || by < 0 || bx >= m || bx < 0 || arr[by][bx] == '#'); } now up(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; if (ry < by) { for (int i = 0; ; i++) { ry--; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } ry++; for (int i = 0; ; i++) { by--; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } by++; if (ry == by && rx == bx) by++; } else { for (int i = 0; ; i++) { by--; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } by++; for (int i = 0; ; i++) { ry--; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } ry++; if (ry == by && rx == bx) ry++; } d++; return cur; } now down(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; if (ry > by) { for (int i = 0; ; i++) { ry++; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } ry--; for (int i = 0; ; i++) { by++; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } by--; if (ry == by && rx == bx) by--; } else { for (int i = 0; ; i++) { by++; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } by--; for (int i = 0; ; i++) { ry++; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } ry--; if (ry == by && rx == bx) ry--; } d++; return cur; } now left(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; if (rx < bx) { for (int i = 0; ; i++) { rx--; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } rx++; for (int i = 0; ; i++) { bx--; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } bx++; if (ry == by && rx == bx) bx++; } else { for (int i = 0; ; i++) { bx--; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } bx++; for (int i = 0; ; i++) { rx--; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } rx++; if (ry == by && rx == bx) rx++; } d++; return cur; } now right(now cur) { auto& [ry, rx, by, bx, d, s, f] = cur; if (rx > bx) { for (int i = 0; ; i++) { rx++; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } rx--; for (int i = 0; ; i++) { bx++; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } bx--; if (ry == by && rx == bx) bx--; } else { for (int i = 0; ; i++) { bx++; if (chkB(cur)) break; if (arr[by][bx] == 'O') { s = true; break; } } bx--; for (int i = 0; ; i++) { rx++; if (chkR(cur)) break; if (arr[ry][rx] == 'O') { f = true; break; } } rx--; if (ry == by && rx == bx) rx--; } d++; return cur; } void bfs(int ry, int rx, int by, int bx) { visited[ry][rx][by][bx] = true; queue q; q.push({ ry,rx,by,bx,0,false,false }); while (!q.empty()) { now cur = q.front(); q.pop(); now nxt = up(cur); if(nxt.finish && !nxt.stop) { cout << nxt.depth; return; } if (!nxt.stop && !visited[nxt.ry][nxt.rx][nxt.by][nxt.bx]) { visited[nxt.ry][nxt.rx][nxt.by][nxt.bx] = true; q.push(nxt); } now nxt1 = down(cur); if (nxt1.finish && !nxt1.stop) { cout << nxt1.depth; return; } if (!nxt1.stop && !visited[nxt1.ry][nxt1.rx][nxt1.by][nxt1.bx]) { visited[nxt1.ry][nxt1.rx][nxt1.by][nxt1.bx] = true; q.push(nxt1); } now nxt2 = left(cur); if (nxt2.finish && !nxt2.stop) { cout << nxt2.depth; return; } if (!nxt2.stop && !visited[nxt2.ry][nxt2.rx][nxt2.by][nxt2.bx]) { visited[nxt2.ry][nxt2.rx][nxt2.by][nxt2.bx] = true; q.push(nxt2); } now nxt3 = right(cur); if (nxt3.finish && !nxt3.stop) { cout << nxt3.depth; return; } if (!nxt3.stop && !visited[nxt3.ry][nxt3.rx][nxt3.by][nxt3.bx]) { visited[nxt3.ry][nxt3.rx][nxt3.by][nxt3.bx] = true; q.push(nxt3); } } cout << -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int rx, ry, bx, by; 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') { ry = i; rx = j; } else if (arr[i][j] == 'B') { by = i; bx = j; } } } bfs(ry, rx, by, bx); return 0; }

제출 #44594

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: