[伯俊/python/13459]仙丹を脱出

質問リンク:パチンコ
これは月が昇る問題と似ているが、条件はもっと厳しい.

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int, input().split())
board=[]
dx=[0,0,-1,1]
dy=[1,-1,0,0]

def bfs(rx,ry,bx,by):
    q=deque()
    q.append((rx,ry,bx,by))
    visited=[]
    visited.append((rx,ry,bx,by))
    count=0
    while q:
        for _ in range(len(q)):
            rx,ry,bx,by=q.popleft()
            if count>10:
                print(0)
                return
            if board[rx][ry]=='O':
                print(1)
                return
            for i in range(4):
                now_rx,now_ry=rx,ry
                while True:
                    now_rx+=dx[i]
                    now_ry+=dy[i]
                    if board[now_rx][now_ry]=='#':
                        now_rx-=dx[i]
                        now_ry-=dy[i]
                        break
                    if board[now_rx][now_ry]=='O':
                        break
                now_bx,now_by=bx,by
                while True:
                    now_bx += dx[i]
                    now_by += dy[i]
                    if board[now_bx][now_by] == '#':
                        now_bx -= dx[i]
                        now_by -= dy[i]
                        break
                    if board[now_bx][now_by] == 'O':
                        break
                if board[now_bx][now_by]=='O':
                    continue
                if now_rx==now_bx and now_ry==now_by:
                    if abs(now_rx-rx)+abs(now_ry-ry)>abs(now_bx-bx)+abs(now_by-by):
                        now_rx-=dx[i]
                        now_ry-=dy[i]
                    else:
                        now_bx-=dx[i]
                        now_by-=dy[i]
                if (now_rx,now_ry,now_bx,now_by) not in visited:
                    q.append((now_rx,now_ry,now_bx,now_by))
                    visited.append((now_rx,now_ry,now_bx,now_by))
        count+=1
    print(0)


for i in range(n):
    board.append(list(input()))
    for j in range(m):
        if board[i][j]=='R':
            rx,ry=i,j
        elif board[i][j]=='B':
            bx,by=i,j

bfs(rx,ry,bx,by)

実現は複雑な問題である.青いボールが先に穴に入ると、青いボールと赤いボールが重なる場合は背中を計算します.最初はなぜアクセス経路をアクセス配列に積み上げたのかと思っていましたが、1つずつ移動するのではなく、壁にぶつかるまで移動するのでアクセス配列は大きくなりませんでした.