#include #include #include using namespace std; typedef struct { int r, c; } POS; int N, M; int minTime = 11; char map[11][11]; POS redBall; POS blueBall; void process(int dir, int step) { bool flag = false; bool gameOver = false; POS curR = redBall; POS curB = blueBall; if (step != 0) { if (dir == 0) { // up if (curR.r < curB.r) { int ny = curR.r; for (ny; ny >= 1; ny--) { if (map[ny - 1][curR.c] == '#') break; if (map[ny - 1][curR.c] == 'O') { flag = true; break; } } if (map[ny - 1][curR.c] == 'O') map[curR.r][curR.c] = '.'; else if (ny != curR.r) { map[ny][curR.c] = 'R'; map[curR.r][curR.c] = '.'; redBall.r = ny; } ny = curB.r; for (ny; ny >= 1; ny--) { if (map[ny - 1][curB.c] == '#' || map[ny - 1][curB.c] == 'R') break; if (map[ny - 1][curB.c] == 'O') { gameOver = true; break; } } if (map[ny - 1][curB.c] == 'O') map[curB.r][curB.c] = '.'; else if (ny != curB.r) { map[ny][curB.c] = 'B'; map[curB.r][curB.c] = '.'; blueBall.r = ny; } } else { int ny = curB.r; for (ny; ny >= 1; ny--) { if (map[ny - 1][curB.c] == '#') break; if (map[ny - 1][curB.c] == 'O') { gameOver = true; break; } } if (map[ny - 1][curB.c] == 'O') map[curB.r][curB.c] = '.'; else if (ny != curB.r) { map[ny][curB.c] = 'B'; map[curB.r][curB.c] = '.'; blueBall.r = ny; } if (!gameOver) { ny = curR.r; for (ny; ny >= 1; ny--) { if (map[ny - 1][curR.c] == '#' || map[ny - 1][curR.c] == 'B') break; if (map[ny - 1][curR.c] == 'O') { flag = true; break; } } if (map[ny - 1][curR.c] == 'O') map[curR.r][curR.c] = '.'; else if (ny != curR.r) { map[ny][curR.c] = 'R'; map[curR.r][curR.c] = '.'; redBall.r = ny; } } } } else if (dir == 1) { // down if (curR.r > curB.r) { int ny = curR.r; for (ny; ny <= N - 2; ny++) { if (map[ny + 1][curR.c] == '#') break; if (map[ny + 1][curR.c] == 'O') { flag = true; break; } } if (map[ny + 1][curR.c] == 'O') map[curR.r][curR.c] = '.'; else if (ny != curR.r) { map[ny][curR.c] = 'R'; map[curR.r][curR.c] = '.'; redBall.r = ny; } ny = curB.r; for (ny; ny <= N - 2; ny++) { if (map[ny + 1][curB.c] == '#' || map[ny + 1][curB.c] == 'R') break; if (map[ny + 1][curB.c] == 'O') { gameOver = true; break; } } if (map[ny + 1][curB.c] == 'O') map[curB.r][curB.c] = '.'; else if (ny != curB.r) { map[ny][curB.c] = 'B'; map[curB.r][curB.c] = '.'; blueBall.r = ny; } } else { int ny = curB.r; for (ny; ny <= N - 2; ny++) { if (map[ny + 1][curB.c] == '#') break; if (map[ny + 1][curB.c] == 'O') { gameOver = true; break; } } if (map[ny + 1][curB.c] == 'O') map[curB.r][curB.c] = '.'; else if (ny != curB.r) { map[ny][curB.c] = 'B'; map[curB.r][curB.c] = '.'; blueBall.r = ny; } if (!gameOver) { ny = curR.r; for (ny; ny <= N - 2; ny++) { if (map[ny + 1][curR.c] == '#' || map[ny + 1][curR.c] == 'B') break; if (map[ny + 1][curR.c] == 'O') { flag = true; break; } } if (map[ny + 1][curR.c] == 'O') map[curR.r][curR.c] = '.'; else if (ny != curR.r) { map[ny][curR.c] = 'R'; map[curR.r][curR.c] = '.'; redBall.r = ny; } } } } else if (dir == 2) { // left if (curR.c < curB.c) { int nx = curR.c; for (nx; nx >= 1; nx--) { if (map[curR.r][nx - 1] == '#') break; if (map[curR.r][nx - 1] == 'O') { flag = true; break; } } if (map[curR.r][nx - 1] == 'O') map[curR.r][curR.c] = '.'; else if (nx != curR.c) { map[curR.r][nx] = 'R'; map[curR.r][curR.c] = '.'; redBall.c = nx; } nx = curB.c; for (nx; nx >= 1; nx--) { if (map[curB.r][nx - 1] == '#' || map[curB.r][nx - 1] == 'R') break; if (map[curB.r][nx - 1] == 'O') { gameOver = true; break; } } if (map[curB.r][nx - 1] == 'O') map[curB.r][curB.c] = '.'; else if (nx != curB.c) { map[curB.r][nx] = 'B'; map[curB.r][curB.c] = '.'; blueBall.c = nx; } } else { int nx = curB.c; for (nx; nx >= 1; nx--) { if (map[curB.r][nx - 1] == '#') break; if (map[curB.r][nx - 1] == 'O') { gameOver = true; break; } } if (map[curB.r][nx - 1] == 'O') map[curB.r][curB.c] = '.'; else if (nx != curB.c) { map[curB.r][nx] = 'B'; map[curB.r][curB.c] = '.'; blueBall.c = nx; } if (!gameOver) { nx = curR.c; for (nx; nx >= 1; nx--) { if (map[curR.r][nx - 1] == '#' || map[curR.r][nx - 1] == 'B') break; if (map[curR.r][nx - 1] == 'O') { flag = true; break; } } if (map[curR.r][nx - 1] == 'O') map[curR.r][curR.c] = '.'; else if (nx != curR.c) { map[curR.r][nx] = 'R'; map[curR.r][curR.c] = '.'; redBall.c = nx; } } } } else { // right if (curR.c > curB.c) { int nx = curR.c; for (nx; nx <= M - 2; nx++) { if (map[curR.r][nx + 1] == '#') break; if (map[curR.r][nx + 1] == 'O') { flag = true; break; } } if (map[curR.r][nx + 1] == 'O') map[curR.r][curR.c] = '.'; else if (nx != curR.c) { map[curR.c][nx] = 'R'; map[curR.r][curR.c] = '.'; redBall.c = nx; } nx = curB.c; for (nx; nx <= M - 2; nx++) { if (map[curB.r][nx + 1] == '#' || map[curB.r][nx + 1] == 'R') break; if (map[curB.r][nx + 1] == 'O') { gameOver = true; break; } } if (map[curB.r][nx + 1] == 'O') map[curB.r][curB.c] = '.'; else if (nx != curB.c) { map[curB.r][nx] = 'B'; map[curB.r][curB.c] = '.'; blueBall.c = nx; } } else { int nx = curB.c; for (nx; nx <= M - 2; nx++) { if (map[curB.r][nx + 1] == '#') break; if (map[curB.r][nx + 1] == 'O') { gameOver = true; break; } } if (map[curB.r][nx + 1] == 'O') map[curB.r][curB.c] = '.'; else if (nx != curB.c) { map[curB.r][nx] = 'B'; map[curB.r][curB.c] = '.'; blueBall.c = nx; } if (!gameOver) { nx = curR.c; for (nx; nx <= M - 2; nx++) { if (map[curR.r][nx + 1] == '#' || map[curR.r][nx + 1] == 'B') break; if (map[curR.r][nx + 1] == 'O') { flag = true; break; } } if (map[curR.r][nx + 1] == 'O') map[curR.r][curR.c] = '.'; else if (nx != curR.c) { map[curR.r][nx] = 'R'; map[curR.r][curR.c] = '.'; redBall.c = nx; } } } } } if (gameOver) return; if (flag || step == 11) { minTime = min(minTime, step); return; } for (int k = 0; k < 4; k++) { char tmp[11][11]; POS tmpRed, tmpBlue; tmpRed = redBall, tmpBlue = blueBall; memcpy(tmp, map, sizeof(tmp)); if (k == 1 && step == 10) { int a; a = 1; } process(k, step + 1); redBall = tmpRed, blueBall = tmpBlue; memcpy(map, tmp, sizeof(map)); } return; } int main(void) { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N >> M; for (int i = 0; i < N; i++) { string str; cin >> str; for (int j = 0; j < M; j++) { map[i][j] = str[j]; if (map[i][j] == 'R') redBall = { i,j }; if (map[i][j] == 'B') blueBall = { i,j }; } } process(-1, 0); if (minTime == 11) minTime = -1; cout << minTime << "\n"; return 0; }

제출 #64626

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: