差分

このページの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://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-01-10abc-151|[AtCoder 参加感想] 2019/01/10:ABC 151 | maspyのHP]]   * [[https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-01-10abc-151|[AtCoder 参加感想] 2019/01/10:ABC 151 | maspyのHP]]
programming_algorithm/grid.txt · 最終更新: 2020/08/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0