差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

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