1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from heapq import *
from collections import deque
dr, dc = (-1,1,0,0), (0,0,-1,1)#udlr
def solution(board0):
    n = len(board0)
    board = [[1 for x in range(n+2)] for xx in range(n+2) ]
    for r in range(n):
        for c in range(n):
            board[r+1][c+1] = board0[r][c]
    answer = 0

    q= [(0,(1,1),(1,1))]
    q = deque(q)
    visited ={}
    while q:
        cnt,cur,vec = q.popleft()
        # cnt,cur,vec = heappop(q)
        r,c = cur

        if (r,c,vec) in visited and visited[(r,c,vec)] <= cnt:
            continue
        visited[(r,c,vec)]=cnt

        for d in range(4):
            nr, nc = r+dr[d], c+dc[d]            
            dot = vec[0]*dr[d] + vec[1]*dc[d]

            if board[nr][nc]<1:
                if dot==0:
                    q.append((cnt+100+500,(nr,nc),(dr[d],dc[d])))
                    # heappush(q, (cnt+100+500,(nr,nc),(dr[d],dc[d])))
                else:
                    q.append((cnt+100,(nr,nc),(dr[d],dc[d])))
                    # heappush(q, (cnt+100,(nr,nc),(dr[d],dc[d])))
    # print(visited)  
    return min([visited[(n,n,(dr[x],dc[x]))] for x in range(4) if (n,n,(dr[x],dc[x])) in visited])