This is my code of Problem D of AtCoder Beginner Contest 308.

atcoder-abc-308-d.py

from collections import deque
import itertools

# 入力
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

# snuke系定数
snuke_len = 5
snuke_list = ["s", "n", "u", "k", "e"]
snuke_set = {"s", "n", "u", "k", "e"}

# あるマスに対して、次のマスになりうるマスの一覧を作成
linked_cells = [[set() for _ in range(W)] for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if S[i][j] not in snuke_set:
        continue
    for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= x < H and 0 <= y < W and S[x][y] == snuke_list[(snuke_list.index(S[i][j]) + 1) % snuke_len]:
            linked_cells[i][j].add((x, y))

# deque型の変数を作成(まずは(0,0)からどのマスへ行けるかを調べるため, (0,0)を格納)
queue = deque([(0, 0)])

# (0, 0)からどのマスに行けるか調べている段階で、一度確認したマスのリスト
# (0, 0)から(0, 0)へは訪れたことにする(Trueにする)
visited = [[False for _ in range(W)] for _ in range(H)]
visited[0][0] = True

# 幅優先探索の実行
# queueの各要素について、隣接するマスを調べる
while queue:
    i, j = queue.popleft()
    for k, l in linked_cells[i][j]:
        # マス(H - 1, W - 1)に到達出来たら、Yesを出力し終了
        if (k, l) == (H - 1, W - 1):
            print("Yes")
            exit()
        # (i, j)から進めることが新たに判明したマス(k, l)に対し、
        # ・visited[k][l]をTrueにし, 
        # ・queueに(k, l)を追加する
        # 新たに進めることが判明したわけではないマス(k, l)に対してはスキップ(continue)
        if visited[k][l]:
            continue
        visited[k][l] = True
        queue.append((k, l))

# マス(H - 1, W - 1)に到達出来なかったので、Noを出力し終了
print("No")