文字列 snuke の中に,同じ文字は使われていない. よって,同じマスを通る必要はない. DFS で実装可能.
一般化:
もし,文字列 snuke の代わりに,同じ文字が現れる文字列 \(S\) の場合. 訪れたかどうかを,\(x \in H, y \in W, i \in Length(S)\) に対して
\(vis: (x,y,i) \mapsto true or false \)
で管理して,同じ状態 \*1;
AtCoder Beginner Contest 308D
bool f = false;
auto dfs = [&](auto dfs, ll cx, ll cy, ll k = 0) -> void {
if(t[k] != s[cx][cy]) return;
if(cx == h-1 && cy == w-1) {
f = true;
return;
}
if(vis[cx][cy]){
return;
}
vis[cx][cy] = true;
vll dx = {-1,0,1,0};
vll dy = {0,-1,0,1};
rep(i,4){
ll nx = dx[i] + cx;
ll ny = dy[i] + cy;
if(!in(nx, h)) continue;
if(!in(ny, w)) continue;
dfs(dfs, nx, ny, (k+1)%5);
}
};
dfs(dfs, 0,0);
yesno(f);
return 0;
}
*1:x,y,i)\) になったら,それ以降は調べなくてよい. なぜなら,座標 \((x,y)\) と \(i\) 文字目の情報があれば, それ以降は同じだから.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w; cin >> h >> w;
cinv(s);
string t = "snuke";
vvll vis(h, vll(w