Skip to content →

構築

作成 2022年7月21日、 最終更新 2022年7月21日

\(H \times W\) のグリッドがある。周囲１マス（\(\max(|dx|,|dy|)=1\)）に移動できる。(0, 0), (x, y) を端点とするハミルトンパスを構築せよ。(ABC232H)

\(H \times W\) のグリッドグラフは

  • \(H \times (W-1)\) と \(H \times 1\) のグリッド
  • \((H-1) \times W\) と \(1 \times W\) のグリッド

に分けられることを用いて部分問題に帰着する。

Published in データ構造

2 Comments

    • 37zigen 37zigen

      本当ですね！ 数式ガチャガチャして解いていたので、勉強になりました。

      2022年9月21日 Reply

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA