答え
ABC308 Dは、左上から右下へ、文字が s → n → u → k → e → s の順になる経路があるかを判定する問題です。まず grid[0][0] が s でなければ No とします。
始点が s なら、現在の文字からsnukeの順で次に必要な文字を持つ、上下左右の未訪問セルだけをキューへ追加します。キューを空にした後、右下の seen[H - 1][W - 1] が True なら Yes、False なら No です。出力するのは条件を満たす経路の有無で、移動回数の数値は出力しません。
BFSで条件付きグリッドを探索する
グリッドの各セルをグラフの頂点とみなし、辺を共有する上下左右のセルの間に辺を張ると、グリッド上の移動をグラフ探索として考えられます。斜めに接するセルは辺で結ばれていないため、候補に含めません。
どの移動もコスト1の重みなしグラフなので、幅優先探索（BFS）を使えます。BFSは先に見つけたセルから順にキューへ入れ、FIFO（先に入れた要素を先に取り出す）の順序で処理します。そのため、始点から0回、1回、2回と移動回数が増える層を保ったまま探索できます。距離を保存する実装ならこの層を最短距離に利用できますが、今回のコードは距離配列を作らず、到達の有無だけを判定します。
Pythonではcollections.dequeの右端へセルを追加し、popleft()で左端から取り出すと、BFSのFIFOを実装できます。
| 現在の文字 | 次に必要な文字 |
|---|---|
s |
n |
n |
u |
u |
k |
k |
e |
e |
s |
sから始めてeまで進んだら、次に必要な文字は再びsです。キューへ入れる状態はセルの座標 (r, c) だけです。入力の各セルの文字は固定され、snukeの5文字は周期の中でそれぞれ一度ずつ現れるため、その座標へ条件を満たして到達したときの周期位置はセルの文字から一意に決まります。同じ座標を別の周期位置として持つ必要がないので、この実装では seen[r][c] だけで重複訪問を防げます。
ABC308 Dの条件と公式例
ABC308 D Snuke Mazeは、H行W列のグリッドで、左上の(1,1)から右下の(H,W)まで進めるかを判定する問題です。訪問するセルの文字は、始点から順にsnukeの周期に一致していなければなりません。
制約は 2 <= H <= 500、2 <= W <= 500 で、各行は小文字英字W文字です。問題文の座標は1始まりですが、Pythonコードでは左上を (0, 0)、右下を (H - 1, W - 1) として扱います。公式の考え方はABC308 Dの公式Editorialでも確認できます。
公式例を追跡する
入力例1
2 3
sns
euk始点 (1,1) の文字は s です。右隣の (1,2) の n、下の (2,2) の u、右の (2,3) の k へ進めるので、ゴールへ到達できます。4セルを通る3回の移動で、出力は Yes です。ここで数えている移動回数は経路の確認用であり、掲載コードの出力項目ではありません。
入力例2
2 2
ab
cd左上の文字が a で始点条件を満たさないため、出力は No です。
入力例3
5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukkuこの入力の出力は Yes です。
Pythonの完全コード
始点の確認、入力、条件付きの4近傍探索、ゴール判定までを一つにした参考コードです。
from collections import deque
H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]
if grid[0][0] != 's':
print('No')
else:
next_char = {'s': 'n', 'n': 'u', 'u': 'k', 'k': 'e', 'e': 's'}
seen = [[False] * W for _ in range(H)]
seen[0][0] = True
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if not (0 <= nr < H and 0 <= nc < W):
continue
if seen[nr][nc]:
continue
if grid[nr][nc] != next_char[grid[r][c]]:
continue
seen[nr][nc] = True
queue.append((nr, nc))
print('Yes' if seen[H - 1][W - 1] else 'No')コードの条件と終了位置
grid[0][0] が s のときだけ、seen[0][0] を True にして始点をキューへ入れます。始点が s でなければ、探索を始めずに No を出力します。
dr, dc の4組が下・上・右・左を表します。候補 (nr, nc) が 0 <= nr < H かつ 0 <= nc < W を満たすか先に確認してから、grid[nr][nc] の文字を読みます。範囲外、すでに seen のセル、next_char[grid[r][c]] と異なるセルは追加しません。条件を満たすセルは、seen[nr][nc] を True にしてからキューへ追加します。
while queue はキューが空になるまで続きます。ゴールが seen[H - 1][W - 1] になった時点で、条件を満たす到達の有無は論理的に確定しますが、このコードはその後も残りのキューを処理し、キューが空になってから最終判定を行います。ゴールの次の文字は要求しません。
正しさと計算量
始点は s であることを確認してからキューへ入ります。その後にキューへ入るセルは、直前のセルと上下左右で接し、グリッド内にあり、snukeの次の文字に一致し、まだ seen ではないという条件をすべて満たします。したがって、seen になった各セルには、始点から文字条件を満たす経路が続いています。
逆に、文字条件を満たす経路上の次のセルは、直前のセルを取り出したときに4方向の候補として調べられます。未訪問ならキューへ入り、すでに訪問済みなら、先に同じ条件を満たす経路でそのセルへ到達済みです。この処理を繰り返すため、条件を満たす経路があればゴールも seen になります。以上から、ゴールの seen が True になることと、条件を満たす経路が存在することは一致します。
各セルは seen を True にした時点で高々一度だけキューへ入り、取り出すたびに確認する方向は4つです。そのため、このPython実装の計算量は O(HW) 時間、seen とキューを合わせた追加メモリは O(HW) です。
小さな入力で検算する
始点とゴールのケース
始点がsでない反例
2 2
an
au掲載コードの最初にある grid[0][0] != 's' のガードを外し、左上が a の入力をそのまま探索すると、最初に取り出した (0, 0) で next_char[grid[r][c]] を評価する際に、辞書にキー a がないため KeyError が発生します。この入力を探索前に No として止めるため、始点の s 確認は独立した条件として必要です。
4セルを3回の移動で通る例
2 3
snu
xxk(1,1)s → (1,2)n → (1,3)u → (2,3)k と進めるため、出力は Yes です。セルを4つ通りますが、移動は3回です。
ゴールへ届かない例
2 3
snx
xxks の次に n までは進めますが、その先に必要な u がないため、ゴールの k へは届かず No です。
| ケース | 期待出力 | 実行結果 |
|---|---|---|
| 公式入力例1 | Yes |
Yes |
| 公式入力例2 | No |
No |
| 公式入力例3 | Yes |
Yes |
| 始点がsでない反例 | No |
No |
| 4セルを3移動で通る例 | Yes |
Yes |
| ゴールへ届かない例 | No |
No |
表は掲載した参考コードをこの6ケースへ実行した結果です。AtCoderへの提出結果や判定を示すものではありません。新しい入力を試すときは、始点が s か、各移動が上下左右か、次の文字がsnukeの順か、ゴールまでの移動回数と通過セル数が一致していないかを順に確認すると、判定を追いやすくなります。
