abc 176 D - Wizard in Maze (python)

atcoder 再開。水色になった。
01-bfs というやつらしい。+0 を append で、+1 に遷移するものを appendleft でdeque に入れてあげると、O(1) で heap みたいなことができる。heap で回したら TLE した。
よくある bfs や今回初めて書いた 5*5 の移動をメモしたかったのでまとめた。

import sys
input = sys.stdin.readline
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
a = [list(input()) for i in range(h)]

d = [[10**6]*w for i in range(h)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
dx = [0,0,1,1,1,1,2,2,2,2,2,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dy = [2,-2,2,1,-1,-2,-2,-1,0,1,2,2,1,-1,-2,2,1,0,-1,-2]

from collections import deque

que = deque()
que.append((sh-1,sw-1,0))
d[sh-1][sw-1] = 0
while que:
    y,x,p = que.pop()
    if y == gh and x == gw:
      break
    for i in range(4):
      nw = x + dw[i]
      nh = y + dh[i]

      if 0 <= nw < w and 0 <= nh < h and a[nh][nw] != "#" and d[nh][nw] > p:
        que.append((nh,nw,p))
        d[nh][nw] = p
        
    for j in range(20):
        nx = x + dx[j]
        ny = y + dy[j]

        if 0 <= nx < w and 0 <= ny < h and a[ny][nx] != "#" and d[ny][nx] > p+1:
          que.appendleft((ny,nx,p+1))
          d[ny][nx] = p+1
          
if d[gh-1][gw-1] == 10**6:
  print(-1)
else:
  print(d[gh-1][gw-1])