省エネなコードを書きたい!

競プロについて書いたりします

気ままに考察/ABC184-E/Third Avenue

問題はこちら。
atcoder.jp
【初考】
 テレポートでなければ普通に幅優先探索で行けそう。先にテレポート無しを計算しておいて、「aを使う場合」とかで別で計算するのかな〜とか......。二回同じ英文字に対しテレポートをする必要がないことはすぐわかる。うまいことテレポートを扱う方法は結局わからず。
【解答】
 二通りあって01BFSの方がめちゃめちゃ綺麗で感動したので記しておく。
 テレポートを使う場合について各テレポートにcost[t]のような形でコストを持たせておく。通常の幅優先探索に加え、テレポートを使う場合(i,j)からa[i][j]のアルファベットに重さ1の辺を、a[i][j]からテレポート先一覧に重さ0の辺を張ることで01BFSができる(テレポート先一覧は前持って作っておく)。
 特別なノードに対して状態を分ける(今回でいうアルファベット、その座標とアルファベットを別々に独立させてグラフを作るみたいな)っていう考え方はよくある気がする。
【コード】
解説写経しました.....感動しすぎて......
atcoder.jp
【感想】
 Eすら見れずに終わったので次こそは......