差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:grid [2020/07/29] – [実装例] ikatakos | programming_algorithm:grid [2020/07/31] – [上下左右への探索] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
====== グリッド ====== | ====== グリッド ====== | ||
- | 2次元をグリッド上に区切ったマス目の上で、何かを考えることがある。 | + | 競技プログラミングでは、2次元をグリッド上に区切ったマス目の上で、何かをした結果を求める、という問題がある。 |
===== 上下左右への探索 ===== | ===== 上下左右への探索 ===== | ||
行 12: | 行 12: | ||
....#G | ....#G | ||
- | これは、そのまま実装すると、以下のような課題が発生する。 | + | これは、素直に盤面を2次元配列で実装すると以下のような課題が発生する。 |
* 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | ||
- | * 現在位置を $(x,y)$ の2値で持たないといけないので、計算量が僅かに増加する | + | * 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する |
いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | ||
行 21: | 行 21: | ||
* [[https:// | * [[https:// | ||
- | 全体を壁で覆い、グリッド内かどうかのチェックを不要にする | + | 全体を壁で覆い、グリッド内かどうかのチェックを壁判定にまとめる |
######## | ######## | ||
#S.#...# | #S.#...# |