競技プログラミング用知識集積所

ABC420D - Toggle Maze

最終更新：2025年08月29日 00:45

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

迷路の最短距離といえば、幅優先探索※。
ただし、迷路の通行可能条件が変わることがあるので、頂点倍加※を行って考える。
つまり、H*Wマスそれぞれ、「oのところが通れる」「xのところが通れる」で頂点を分けて、2*H*W頂点の3次元グリッドとして幅優先探索をする。

あとは気合の実装力勝負。
グリッドの一次元化※を行うか、3次元のままやるか、どちらが楽かは好み次第。

タグ：

幅優先探索頂点倍加

競技プログラミング用知識集積所

記事メニュー

人気タグ「」関連ページ

人気記事ランキング

最近更新されたページ

急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！