구슬 탈출 - BOJ

구슬 탈출 - BOJ

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def slope(x, y, tx, ty, c):
    while board[x + tx][y + ty] != '#' and board[x][y] != 'O':
        x += tx
        y += ty
        c += 1
    return x, y, c

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
visit = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
q = deque()

for i in range(N):
    for j in range(M):
        if board[i][j] == 'R':
            x1, y1 = i, j
        elif board[i][j] == 'B':
            x2, y2 = i, j
q.append([x1, y1, x2, y2, 0])
visit[x1][y1][x2][y2] = True


while q:
    x1, y1, x2, y2, cnt = q.popleft()
    if cnt >= 10:
        break
    for i in range(4):
        nx1, ny1, c1 = slope(x1, y1, dx[i], dy[i], 0)
        nx2, ny2, c2 = slope(x2, y2, dx[i], dy[i], 0)

        if board[nx2][ny2] == 'O':
            continue
        if board[nx1][ny1] == 'O':
            print(1)
            exit(0)
        if nx1 == nx2 and ny1 == ny2:
            if c1 > c2:
                nx1 -= dx[i]
                ny1 -= dy[i]
            else:
                nx2 -= dx[i]
                ny2 -= dy[i]
        if not visit[nx1][ny1][nx2][ny2]:
            visit[nx1][ny1][nx2][ny2] = True
            q.append([nx1, ny1, nx2, ny2, cnt + 1])
print(0)