各マスを頂点とした有向グラフ \(G\) を考えます。以下の条件を満たすマスの組 \((i_1,j_1),(i_2,j_2)\) に対して、\((i_1,j_1)\) から \((i_2,j_2)\) に向かって辺を張ります。

• \((i_1,j_1)\) と \((i_2,j_2)\) は辺で隣接する
• \((i_1,j_1)\) に書かれた文字は s,n,u,k,e のいずれかである
• \((i_1,j_1)\) に書かれた文字が s であるならば、\((i_2,j_2)\) に書かれた文字は n である
• \((i_1,j_1)\) に書かれた文字が n であるならば、\((i_2,j_2)\) に書かれた文字は u である
• \(\vdots\)
• \((i_1,j_1)\) に書かれた文字が e であるならば、\((i_2,j_2)\) に書かれた文字は s である

このとき、問題文中の条件は、\(G\) 上で \((1,1)\) から \((H,W)\) へのパスが存在することと同値です。よって、\(G\) 上で DFS や BFS をすることで、この問題を \(O(HW)\) で解くことができます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

const vector<int> dx = {0, 0, 1, -1};
const vector<int> dy = {1, -1, 0, 0};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) cin >> s[i];
    if (s[0][0] != 's') {
        cout << "No" << endl;
        return 0;
    }
    vector<char> next(256);
    next['s'] = 'n';
    next['n'] = 'u';
    next['u'] = 'k';
    next['k'] = 'e';
    next['e'] = 's';
    vector seen(h, vector<bool>(w));
    auto dfs = [&](auto &dfs, int i, int j) -> void {
        seen[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (s[ni][nj] != next[s[i][j]]) continue;
            if (seen[ni][nj]) continue;
            dfs(dfs, ni, nj);
        }
    };
    dfs(dfs, 0, 0);
    cout << (seen[h - 1][w - 1] ? "Yes" : "No") << endl;
}