[알고리즘] 백준 15653 구슬 탈출 4 / 파이썬

www.acmicpc.net/problem/15653

15653번: 구슬 탈출 4

 

from collections import deque

def move(x, y, dx, dy):
    m = 0
    while True:
        if B[x][y] == 'O':
            break
        if B[x][y] == '#':
            x -= dx
            y -= dy
            break
        x += dx
        y += dy
        m += 1
    return x, y, m

dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
def sol():
    while q:
        result, rx, ry, bx, by = q.popleft()
        for i in range(4):
            mrx, mry, mr = move(rx, ry, dx[i], dy[i])
            mbx, mby, mb = move(bx, by, dx[i], dy[i])
            if B[mbx][mby] == 'O':
                continue
            if B[mrx][mry] == 'O':
                return result
            if mrx == mbx and mry == mby:
                if mr < mb: mbx, mby = mbx-dx[i], mby-dy[i]
                else: mrx, mry = mrx-dx[i], mry-dy[i]
            if ck[mrx][mry][mbx][mby] == 0:
                ck[mrx][mry][mbx][mby] = 1
                q.append([result+1, mrx, mry, mbx, mby])
    return -1

N, M = map(int, input().split(' '))
B = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(M):
        if B[i][j] == 'R':
            rx, ry = i, j
            B[i][j] = '.'
        elif B[i][j] == 'B':
            bx, by = i, j
            B[i][j] = '.'
q = deque()
q.append([1, rx, ry, bx, by])
ck = [[[[0]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
ck[rx][ry][bx][by] = 1
print(sol())