先日，ABC176に参加した． 私はE問題が解けず4完だったが，DとEは両方緑diffだったようだ．．．．恐ろしい．
それはそうと，コンテスト中に書いたABC176 D - Wizard in Mazeの解法が解説とは違っていたので，解法をここに残しておく．
提出したコードは下記に．
提出 #16156606 - AtCoder Beginner Contest 176
ほぼ表題の通り．
迷路をグラフと捉え， 壁でないマスに対して，それぞれ以下の処理を行う．
- 距離1の壁でないマスに対して，コスト0の辺を貼る
- 距離2の壁でないマスに対して，コスト1の辺を貼る
次に，マス (C_h, C_w) から 各ノードへの最短距離を求める． これは先の手順で作成したグラフに対してダイクストラ法を適用すれば求めることができる．
すると，マス (D_h, D_w) への最短距離がそのまま答えとなる．
BFSとか0-1BFSとかで解けるらしいけど，思い浮かばなかった．．．．