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