import sys
input = sys.stdin.readline
from collections import deque
dy = [1,0,-1,0]
dx = [0,1,0,-1]
N,M = map(int,input().split())
board = []
for i in range(N):
board.append(list(input().strip()))
def go(y,x,direction,opcolor):
while True:
y1 = y+dy[direction]
x1 = x+dx[direction]
if (y1,x1) == opcolor:
break
if board[y1][x1] == "O":
return 0,0
if board[y1][x1] == ".":
y,x = y1,x1
else:
break
return y,x
def check(y,x,direction):
clear = set()
for i in range(4):
if (i+direction)%2==0 and direction != -1:
continue
y1 = y+dy[i]
x1 = x+dx[i]
if board[y1][x1] != "#":
clear.add(i)
return clear
for i in range(N):
for j in range(M):
if board[i][j] == "R":
red = [i,j]
board[i][j] = "."
if board[i][j] == "B":
blue = [i,j]
board[i][j] = "."
dq = deque()
dq.append((red[0],red[1],blue[0],blue[1],-1,0))
memory = set()
result = -1
while dq:
ry,rx,by,bx,direction,cnt = dq.popleft()
if (ry,rx,by,bx) in memory:
continue
memory.add((ry,rx,by,bx))
if by == 0:
continue
if ry == 0:
result = cnt
break
clearR = check(ry,rx,direction)
clearB = check(by,bx,direction)
for direction in clearR|clearB:
ry1,rx1 = go(ry,rx,direction,(by,bx))
by1,bx1 = go(by,bx,direction,(ry1,rx1))
if ry1:
ry1,rx1 = go(ry1,rx1,direction,(by1,bx1))
dq.append((ry1,rx1,by1,bx1,direction,cnt+1))
print(result)
구슬탈출 1,3처럼 구슬탈출 2 코드로 날먹했다.
구슬탈출 2 코드에서 cnt 제한을 해제하고, 대신 빨간공, 파란공의 현 위치를 memory라는 set를 만들어 그 안에 튜플로 저장한다. 그리고 만약 현 위치가 memory set에 이미 들어있었다면 똑같은 위치로 돌아왔다는 뜻이므로 continue 해준다.
구슬탈출 2만 제대로 풀면 구슬탈출 1,3,4를 전부 1초만에 풀 수 있다 ㅋㅋㅋ
오늘의 교훈) 날먹은 재미있다