ABC 401-500/ABC453D - Go Straight - 競技プログラミング用 知識集積所

---

問題

ABC453D

必要知識

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

• 頂点倍加※
• 幅優先探索※

考え方

迷路なので、典型問題の幅優先探索※ベースで考えればよい。
通常でない点は、同じマスにいるにしても、'o'や'x'のマスではどちらから来たのかによって状況が変わってくる点。
このような場合は頂点倍加※、つまり1マスに来た方向ごとにデータを4つ分割り当てるのが有効。
HとWが最大1000なので、全マス4つずつ情報を割り当てても400万データで済む。

これに気づけばあとは実装力勝負。
マスが何ならどの方向からどの方向へ行けるかがけっこうややこしい。
1つだけ間違えたりするとバグ取りが地獄になるので、丁寧に実装すること。

解答例

解答例

注意点

別解