kira000 https://blog.hatena.ne.jp/kira000/ kira924age’s note https://kira924age.hatenadiary.com/ 競技プログラミング AOJ ICPC 最短経路問題 幅優先探索 問題 https://onlinejudge.u-aizu.ac.jp/problems/1166 問題文 問題概要 迷路を表すデータが与えられる. 入口から出口までの最短経路の長さを求めよ. 制約 データセット数 : 解答例 指針 BFS 解説 二次元グリッド上の最短経路問題なので幅優先探索(Breadth First Search: BFS)をすればいいのは, すぐに分かる. しかし迷路の壁のデータが与えられるという少しトリッキーな形式なので注意が必要. 各座標の4方向に関して, 移動できるかどうかを値として保持するようにすればこの問題を解くことができる. C++ による実装例 // su… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkira924age.hatenadiary.com%2Fentry%2F2019%2F12%2F30%2F234152" title="AOJ 1166: 迷図と命ず / Amazing Mazes - kira924age’s note" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%202%20%5Cleq%20h%2C%20w%20%5Cleq%2030 Hatena Blog https://hatena.blog 2019-12-30 23:41:52 rich https://kira924age.hatenadiary.com/entry/2019/12/30/234152 1.0 100%