abc 184 E - Third Avenue (python)

久しぶりに bfs やら ord を書いたのでメモ。

import sys
input = sys.stdin.readline
h,w = map(int,input().split())
s = [list(input().rstrip()) for i in range(h)]
to = [[] for i in range(26)]
for i in range(h):
  for j in range(w):
    if 96 < ord(s[i][j]) < 124:
      to[ord(s[i][j])-97].append((i,j))
    if s[i][j] == 'S':
      sh = i; sw = j
    if s[i][j] == 'G':
      gh = i; gw = j
      
dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
d = [[4*10**6]*w for i in range(h)]

from collections import deque

que = deque()
que.append((sh,sw,0))
d[sh][sw] = 0
while que:
    y,x,p = que.popleft()
    #print(y,x,p)
    if s[y][x] == 'G':
      break
    for i in range(4):
      nw = x + dw[i]
      nh = y + dh[i]

      if 0 <= nw < w and 0 <= nh < h and d[nh][nw] > p+1:
        if s[nh][nw] == "." or s[nh][nw] == "G":
          que.append((nh,nw,p+1))
          d[nh][nw] = p+1
        
      if 0 <= nw < w and 0 <= nh < h and 96 < ord(s[nh][nw]) < 124 and d[nh][nw] > p+1:
        d[nh][nw] = p+1
        que.append((nh,nw,p+1))
        for hh,ww in to[ord(s[nh][nw])-97]:
          if d[hh][ww] > p+2:
            que.append((hh,ww,p+2))
            d[hh][ww] = p+2
        to[ord(s[nh][nw])-97] = []
        
        
#print(d)
if d[gh][gw] == 4*10**6:
  print(-1)
else:
  print(d[gh][gw])