#include #include #include #include using namespace std; // Down, Left, Up, Right const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; bool visited[10][10][10][10] = {false}; int main() { int N, M; cin >> N >> M; vector> plate(N, vector(M)); pair pos_red, pos_blue, pos_hole; for (int i = 0; i < N; i++) { string line; cin >> line; for (int j = 0; j < M; j++) { plate[i][j] = line[j]; if (plate[i][j] == 'R') { pos_red = {i, j}; plate[i][j] = '.'; } else if (plate[i][j] == 'B') { pos_blue = {i, j}; plate[i][j] = '.'; } else if (plate[i][j] == 'O') pos_hole = {i, j}; } } queue> q_red; queue> q_blue; queue q_count; q_red.push(pos_red); q_blue.push(pos_blue); q_count.push(0); while (!q_red.empty()) { int x_red = q_red.front().first; int y_red = q_red.front().second; int x_blue = q_blue.front().first; int y_blue = q_blue.front().second; int count = q_count.front(); if (count > 10) { cout << -1 << endl; return 0; } q_red.pop(); q_blue.pop(); q_count.pop(); for (int dir = 0; dir <= 3; dir++) { int nx_red = x_red, ny_red = y_red; int nx_blue = x_blue, ny_blue = y_blue; int cnt = count + 1; bool first; // true : red first switch (dir) { case 0: first = (nx_red > nx_blue); break; case 1: first = (ny_red < ny_blue); break; case 2: first = (nx_red < nx_blue); break; case 3: first = (ny_red > ny_blue); break; } // Down(0) -> x좌표 큰거먼저 // Left(1) -> y좌표 작은거먼저 // Up(2) -> x좌표 작은거먼저 // Right(3)-> y좌표 큰거먼저 while (plate[nx_red + dx[dir]][ny_red + dy[dir]] != '#' || plate[nx_blue + dx[dir]][ny_blue + dy[dir]] != '#') { if (first) { if (plate[nx_red + dx[dir]][ny_red + dy[dir]] != '#') { nx_red += dx[dir]; ny_red += dy[dir]; } // 다음칸이 red면 break if (nx_blue + dx[dir] == nx_red && ny_blue + dy[dir] == ny_red) break; // 다음칸이 #이 아니고 red랑 좌표가 안 겹치면 이동 if (plate[nx_blue + dx[dir]][ny_blue + dy[dir]] != '#' && (nx_blue + dx[dir] != nx_red || ny_blue + dy[dir] != ny_red)) { nx_blue += dx[dir]; ny_blue += dy[dir]; } } else { if (plate[nx_blue + dx[dir]][ny_blue + dy[dir]] != '#') { nx_blue += dx[dir]; ny_blue += dy[dir]; } if (nx_red + dx[dir] == nx_blue && ny_red + dy[dir] == ny_blue) break; if (plate[nx_red + dx[dir]][ny_red + dy[dir]] != '#' && (nx_red + dx[dir] != nx_blue || ny_red + dy[dir] != ny_blue)) { nx_red += dx[dir]; ny_red += dy[dir]; } } if (plate[nx_blue][ny_blue] == 'O') break; if (plate[nx_red][ny_red] == 'O') { while (plate[nx_blue + dx[dir]][ny_blue + dy[dir]] != '#') { nx_blue += dx[dir]; ny_blue += dy[dir]; if (nx_blue == nx_red && ny_blue == ny_red) { continue; } } cout << cnt << "\n"; return 0; } } if (cnt > 10) { cout << -1 << "\n"; return 0; } // 하나라도 움직였다면 큐에 추가 if (nx_red != x_red || ny_red != y_red || nx_blue != x_blue || ny_blue != y_blue) { if (plate[nx_blue][ny_blue] == 'O') continue; if (!visited[nx_red][ny_red][nx_blue][ny_blue]) { visited[nx_red][ny_red][nx_blue][ny_blue] = true; q_red.push({nx_red, ny_red}); q_blue.push({nx_blue, ny_blue}); q_count.push(cnt); } } } } cout << -1 << "\n"; return 0; }

제출 #53062

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: