#include #include #include #include #include using namespace std; int maps[11][11]; int n, m; int fy, fx; bool visited[11][11][11][11]; int result = 1000; int mov[4][2] = { {0,1}, {1,0}, {-1,0}, {0,-1} }; tuple return_location(int ry, int rx, int by, int bx, int r) { bool redfirst = false; switch (r) { case 0: redfirst = rx > bx; break; case 1: redfirst = ry > by; break; case 2: redfirst = by > ry; break; case 3: redfirst = bx > rx; break; } if (redfirst) { while (maps[ry + mov[r][0]][rx + mov[r][1]] == 0 && !(ry == fy && rx == fx)) ry += mov[r][0], rx += mov[r][1]; maps[ry][rx] = 1; while (maps[by + mov[r][0]][bx + mov[r][1]] == 0 && !(by == fy && bx == fx)) by += mov[r][0], bx += mov[r][1]; maps[ry][rx] = 0; } else { while (maps[by + mov[r][0]][bx + mov[r][1]] == 0 && !(by == fy && bx == fx)) by += mov[r][0], bx += mov[r][1]; maps[by][bx] = 1; while (maps[ry + mov[r][0]][rx + mov[r][1]] == 0 && !(ry == fy && rx == fx)) ry += mov[r][0], rx += mov[r][1]; maps[by][bx] = 0; } return { ry, rx, by, bx }; } void prt(int ry, int rx, int by, int bx) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (ry == i && rx == j) cout << 'R'; else if(by == i && bx == j) cout << 'B'; else { cout << (maps[i][j] == 0 ? '.' : '#'); } } cout << endl; } } void dfs(int ry, int rx, int by, int bx, int tryy){ if (ry == fy && rx == fx) { result = min(result, tryy); return; } //prt(ry, rx, by, bx); if ((by == fy && bx == fx) || tryy==10) { /*printf("도착 실패\n"); printf("이유: 블루가 먼저 도착함 %d 시도가 오버됨 %d\n", (by == fy && bx == fx), tryy == 10); printf("마지막 위치 %d %d\n\n", ry, rx);*/ return; } //if (visited[ry][rx][by][bx]) return; // 이미 방문한 상태라면 중단 visited[ry][rx][by][bx] = true; for (int i = 0, ryy, rxx, byy, bxx; i < 4; i++) { tie(ryy, rxx, byy, bxx) = return_location(ry, rx, by, bx, i); //printf("%d %d %d %d\n", ryy, rxx, byy, bxx); if (ryy == ry && rxx == rx && byy == by && bxx == bx) continue; dfs(ryy, rxx, byy, bxx, tryy + 1); } //visited[ry][rx][by][bx] = false; } int main() { cin >> n >> m; int ry, rx; int by, bx; string s; for (int i = 0; i < n; i++) { cin >> s; for (int j = 0; j < m; j++) { maps[i][j] = (s[j] == '#' ? 1 : 0); if (s[j] == 'R') ry = i, rx = j; else if (s[j] == 'B') by = i, bx = j; else if (s[j] == 'O') fy = i, fx = j; } } dfs(ry, rx, by, bx, 0); cout << (result == 1000 ? -1 : result); }

제출 #89607

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: