考察
キングは斜めにも一マス進める。通常の蛇行を作って終点だけ入れ替えると未訪問領域を分断しやすいので、「左上 (1,1) から、指定した別のマス (a,b) へ、全マスを一度ずつ通る」という同じ問題を小さい長方形に残す。
まず H=2 を基底にする。次の順に出力する。
- 列 j=1,…,b−1 について (1,j),(2,j) をこの順で出す。
- 終点と同じ列の他方のマス (3−a,b) を出す。
- (1,b+1),…,(1,W)、続いて (2,W),…,(2,b+1) を出す。
- 最後に (a,b) を出す。
b=1 では手順1が空、b=W では手順3が空である。終点が (1,1) ではないという前提により、b=1 なら a=2 で手順2が始点 (1,1) になる。各接続は縦・横・斜めの一歩で、全2Wマスが一度ずつ現れる。W=2,H>2 は行列を交換してこの基底にする。
H,W>2 では S={第一列の全マス}∪{(H,2)} を終点を避ける向きの判定にだけ使う。終点が S に入るなら転置する。転置前の S と転置後の同じ形の S の共通部分は始点 (1,1) だけなので、転置後は終点が S の外になる。
終点が S の外なら、親が出力・除去するのは第一列 (1,1),…,(H,1) だけ。残る H×(W−1) 長方形を上下反転し、子の終点を (H+1−a,b−1) として再帰する。子の座標 (u,v) を元の (H+1−u,v+1) に写して、親の出力へ続ける。子の始点 (1,1) は元の (H,2) なので、親の末尾 (H,1) から一歩で接続する。(H,2) は子だけが出力する。
H=W=3、終点 (3,3) なら例えば
(1,1),(2,1),(3,1),(3,2),(2,2),(1,2),(1,3),(2,3),(3,3)
の9マスになる。S 全体を親が出力すると (3,2) が重複し、残りも長方形でなくなることがわかる。
実装では各再帰の座標変換を元盤面への写像として合成する。子が返す全配列を各階層でコピー・変換するのでなく、確定した列や基底の座標をその写像で共通の出力配列へ追加すれば、一マス当たり定数時間で出力できる。
典型の発動条件
再帰構成で未訪問領域を保つ
発動条件: 固定した帯を通った後に、始点と終点の条件を保つ同型問題が残るとき。
親が消費する帯と、子に含める接続マスを明確に分ける。本問では第一列だけを親が所有し、その右下の接続マスは子の始点にする。
対称変換で場合分けを減らす
発動条件: 行と列が対称で、終点を削る帯の外へ移せるとき。
転置後も始点は左上のままであり、上下反転・平行移動を合成すれば一つの標準再帰を使える。
問題固有の要素
S は出力領域ではなく、子の始点まで含めて終点を避ける判定集合である。除くのは第一列だけなので残りは長方形、(H,2) は残りの始点として一度だけ通る。
別の問題へ持ち帰る視点: 再帰構成では親と子の所有領域を重ならせず、親の末尾と子の先頭が隣接することを確認する。
正当性
H=2 の基底は終点列以外を指定順で使い、他方のマスを先に、終点を最後に置くので全マスを一度ずつ訪問する。空区間でも始点・隣接性は保たれる。H,W>2 では必要なら転置して終点を S の外へ移す。親は第一列だけを訪問するので未訪問領域は H×(W−1) の長方形で、子の始点に対応する (H,2) から親の末尾 (H,1) へ一歩で接続できる。帰納法により子は残りを重複なく訪問し指定終点で終わる。列を削るたび面積が減り、転置は続けて必要にならないため基底へ到達する。
実装上の注意
- S で向きを判定し、第一列だけを親で出力する。(H,2) は子の先頭として一度だけ出す。
- H=2 の基底で b=1,b=W のループを空として扱い、始点や終点を別途重複追加しない。
- 元座標への写像を合成して一つの出力配列へ追加する。各再帰で子の全出力をコピーすると O(HW) という時間上界にはならない。
復習の核
- 構成の特殊ケースが増えたら、固定した帯を訪問した後の未訪問領域が同じ問題になる削り方を探す。
- 再帰構成は出力列を眺めるだけでなく、各段階の開始点・終了点・未訪問長方形の三つを不変条件として検証する。
計算量と制約
時間
O(HW)。各マスを共通の出力配列へ一度だけ追加し、座標変換を一マス当たり O(1) で適用する。再帰状態数は O(H+W)。
空間
O(HW)。出力配列と O(H+W) の再帰stack。逐次出力なら配列を省ける。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq H \leq 100; 2 \leq W \leq 100; 1 \leq a \leq H; 1 \leq b \leq W; (a, b) \neq (1, 1); All values in input are integers.
出典