오호 앞전에 구슬 탈출 3문제를 푸느라 고생했다고 주는 선물일까요
이 문제는 구슬탈출2 에서 cnt 조건만 빼면 답이 나오는 문제네요
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(sys.stdin.readline().rstrip()))
# 방향 정보
dx =[-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(rx, ry, bx, by, cnt):
cnt = 0
visited[rx][ry][bx][by] = True
while q:
for _ in range(len(q)):
rx, ry, bx, by, cnt = q.popleft()
# 빨간 구슬이 구멍을 만나면 카운트 출력
if graph[rx][ry] =='O':
return cnt
for i in range(4):
rnx = rx
rny = ry
bnx = bx
bny = by
# 빨간 구슬이 벽에 닿거나 구멍에 닿을 때 까지 계속 이동
while True:
rnx += dx[i]
rny += dy[i]
# 벽에 닿으면 한 칸 뒤로
if graph[rnx][rny]=='#':
rnx -= dx[i]
rny -= dy[i]
break
# 구멍에 닿으면 멈춰!
if graph[rnx][rny] == 'O':
break
# 파란 구슬도 마찬가지
while True:
bnx += dx[i]
bny += dy[i]
# 벽에 닿으면 한칸 뒤로
if graph[bnx][bny]=='#':
bnx -= dx[i]
bny -= dy[i]
break
# 구멍에 닿으면 멈춰!
if graph[bnx][bny] == 'O':
break
# 근데 파란 구슬이 구멍에 들어가면 안되니까 무시
if graph[bnx][bny] == 'O':
continue
# 두 구슬이 같은 위치에 있을 수 없으니 더 많이 움직인 것이 더 늦게 온것이기 때문에 한칸 뒤로
if rnx == bnx and rny == bny:
if abs(rnx - rx) + abs(rny - ry) > abs(bnx - bx) + abs(bny - by):
rnx -= dx[i]
rny -= dy[i]
else:
bnx -= dx[i]
bny -= dy[i]
# 방문 처리하고 큐에 넣기
if not visited[rnx][rny][bnx][bny]:
visited[rnx][rny][bnx][bny] = True
q.append((rnx, rny, bnx, bny, cnt+1))
return -1
red = []
blue = []
for i in range(n):
for j in range(m):
if graph[i][j] == 'R':
red.append((i, j))
if graph[i][j] == 'B':
blue.append((i, j))
q = deque()
q.append((red[0][0], red[0][1], blue[0][0], blue[0][1], 0))
visited = [[[[False for _ in range(m)]for _ in range(n)]for _ in range(m)]for _ in range(n)]
print(bfs(red[0][0], red[0][1], blue[0][0], blue[0][1], 0))