atcoder ABC D - Snuke Mazeの勉強

・参考：
Editorial - AtCoder Beginner Contest 308

・考え方：参考の通りDFSをして、H,W座標まで行けるのか(seen[h-1][w-1]を探索済みにできるか)をすればいい。snukeの文字の管理、例えば's'のあとに'n'とかはnx={}で辞書型で管理する。

・ACコード：

import sys
sys.setrecursionlimit(10**6)  #再帰関数の回数を10**6まで増やす

h,w=map(int, input().split())
f=[input() for _ in range(h)]

if f[0][0]!='s':
  print("No")
  exit()
  
dx=[1,0,0,-1]
dy=[0,1,-1,0]

seen=[[0 for _ in range(w)]for _ in range(h)]

nx={}   #snukeの単語の次の単語を辞書型で管理。
nx['s']='n'
nx['n']='u'
nx['u']='k'
nx['k']='e'
nx['e']='s'
#print(nx)

def dfs(i,j,f):
  seen[i][j]=1  #探索済みに
  for k in range(4):
    ni=i+dx[k]
    nj=j+dy[k]
      
    if 0>ni or ni>=h or 0>nj or nj>=w:   #場外はスルー
      continue
    if seen[ni][nj]:  #探索済みはスルー
      continue
    if nx[f[i][j]]!=f[ni][nj]:  #i,jから行けるni,njの文字が対応していないときスルー。
      continue
    
    dfs(ni,nj,f)   #全部違かったらdfs

dfs(0,0,f)

print("Yes" if seen[h-1][w-1] else "No")   #seen[h-1][w-1]が探索済み、つまりh,wに到達できたらYes