# BOJ - 13460 - 구슬 탈출 2

Updated:

``````import sys
from collections import deque

def moveCheck(maps, x, y, dx, dy):
count = 0
while maps[x + dx][y + dy] != '#' and maps[x][y] != 'O':
x += dx
y += dy
count += 1
return x, y, count

def BFS(maps, N, M, rx, ry, bx, by):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visit = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
visit[rx][ry][bx][by] = True

dq = deque()
dq.append((rx, ry, bx, by, 1))
while dq:
rx, ry, bx, by, move = dq.popleft()
if move > 10:
break

for k in range(4):
nrx, nry, rCount = moveCheck(maps, rx, ry, dx[k], dy[k])
nbx, nby, bCount = moveCheck(maps, bx, by, dx[k], dy[k])

if maps[nbx][nby] == 'O':
continue

if maps[nrx][nry] == 'O':
return move

if nrx == nbx and nry == nby:
if rCount > bCount:
nrx -= dx[k]
nry -= dy[k]
else:
nbx -= dx[k]
nby -= dy[k]
if not visit[nrx][nry][nbx][nby]:
visit[nrx][nry][nbx][nby] = True
dq.append((nrx, nry, nbx, nby, move + 1))

return -1

def solution():
N, M = map(int, input().split())
maps = []

for _ in range(N):
maps.append(list(str(sys.stdin.readline().strip())))

for i in range(N):
for j in range(M):
if maps[i][j] == 'R':
rx, ry = i, j
elif maps[i][j] == 'B':
bx, by = i, j

print(BFS(maps, N, M, rx, ry, bx, by))

solution()
``````

https://www.acmicpc.net/problem/13460

Categories:

Updated: