ワープ

AtCoder ABC 184 E - Third Avenue (水色, 500 点)

AtCoder AtCoder500点 ABC-E グリッド迷路 BFS ワープ探索問題最短路問題 0-1BFS denseなグラフをスーパーノードでsparseにする水色diff

おおむね BFS だけど、ちょっとだけ TLE に注意。。。問題へのリンク問題概要のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…

グリッド迷路二分探索方程式期待値期待値DP コーナーケース AOJ AOJ-ICPC600点 JAG AOJ-ICPC JAG夏合宿ワープ

グリッド系は苦手意識あるけど解けてよかった問題へのリンク問題概要二次元マップが与えられて、各マスは床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…