【AtCoder】【Python】ABC308 D問題
Snuke Maze

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

nextDict = {'s':'n', 'n':'u', 'u':'k', 'k':'e', 'e':'s'}
snuke = nextDict.keys()

# 次の文字で正しいかを判定する
def isValid(current, next):
    # そもそも文字がsnukeのいずれかで無い場合あり
    if not (current in snuke and next in snuke):
        return False
    # 次の文字で正しいければ 
    if nextDict[current] == next:
        return True
    return False

# キューの準備
que = []
que.append((0, 0))

# 上下左右
add = [(0, 1), (0, -1),(-1, 0), (1, 0)]

# 見たフラグの初期化
seen = [[False]*W for _ in range(H)]
seen[0][0] = True

# キューを用いた、BFS
while que:
    # キューから取り出す
    x, y = que.pop()
     # 見たフラグon
    seen[x][y] = True
    # print(grid[x][y]) # 確認用
    for x1, y1 in add:
        (x2, y2) = (x + x1, y +y1)
        # 枠内でなければ、continue
        if not (0<= x2 < H and 0 <= y2 < W) : continue
        # すでに見ていれば、continue
        if seen[x2][y2]: continue
        # 次の文字でなければ、continue
        if isValid(grid[x][y], grid[x2][y2]) == False: continue
        # 次の文字であれば, キューに加える
        que.append((x2, y2))

# 一番右端のマス（ゴール）まで見たかを判定
print("Yes" if seen[H-1][W-1] else "No")