#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; char board[10][10]; int dist[10][10][10][10]; int dirR[4] = { 1, -1, 0, 0 }; int dirC[4] = { 0, 0, 1, -1 }; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; pair red; pair blue; pair goal; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { char c; cin >> c; board[i][j] = c; if (c == 'R') { red = { i, j }; board[i][j] = '.'; } if (c == 'B') { blue = { i, j }; board[i][j] = '.'; } if (c == 'O') { goal = { i, j }; board[i][j] = '.'; } } } queue, pair>> Q; Q.push({ red, blue }); dist[red.first][red.second][blue.first][blue.second] = 1; int ans = -1; while (!Q.empty() && ans == -1) { pair < pair, pair> cur = Q.front(); Q.pop(); if (dist[cur.first.first][cur.first.second][cur.second.first][cur.second.second] >= 11) break; for (int i = 0; i < 4; i++) { pair curRed = cur.first; pair curBlue = cur.second; pair nextRed = { curRed.first + dirC[i], curRed.second + dirR[i] }; pair nextBlue = { curBlue.first + dirC[i], curBlue.second + dirR[i]}; bool bumpRed = false; bool bumpBlue = false; bool succRed = false; bool succBlue = false; while (board[nextRed.first][nextRed.second] == '.') { curRed = nextRed; if (curRed == cur.second) bumpRed = true; if (curRed == goal) succRed = true; nextRed = { curRed.first + dirC[i], curRed.second + dirR[i] }; } while (board[nextBlue.first][nextBlue.second] == '.') { curBlue = nextBlue; if (curBlue == cur.first) bumpBlue = true; if (curBlue == goal) succBlue = true; nextBlue = { curBlue.first + dirC[i], curBlue.second + dirR[i] }; } if (bumpRed) curRed = { curRed.first - dirC[i], curRed.second - dirR[i] }; if (bumpBlue) curBlue = { curBlue.first - dirC[i], curBlue.second - dirR[i] }; if (dist[curRed.first][curRed.second][curBlue.first][curBlue.second] != 0) continue; if (!succBlue) { if (succRed) { ans = dist[cur.first.first][cur.first.second][cur.second.first][cur.second.second]; break; } Q.push({ curRed, curBlue }); dist[curRed.first][curRed.second][curBlue.first][curBlue.second] = dist[cur.first.first][cur.first.second][cur.second.first][cur.second.second] + 1; } } } cout << ans; return 0; }

제출 #46693

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: