文書の過去の版を表示しています。
グリッド
2次元をグリッド上に区切ったマス目の上で、何かを考えることがある。
上下左右への探索
通行可能なマスと不可能なマスがあり、隣接する上下左右へ移動を繰り返す問題がある。例えば以下の迷路のような問題が代表的。
S.#... ..###. #.#... ....#G
これは、そのまま実装すると、以下のような課題が発生する。
- 一番端のマスから外へ出てはいけないので毎度チェックする必要がある
- 現在位置を $(x,y)$ の2値で持たないといけないので、計算量が僅かに増加する
いずれも些細な問題と言えばそうだが、以下に示すテクニックを使うと、両方解決する。
全体を壁で覆い、グリッド内かどうかのチェックを不要にする ######## #S.#...# #..###.# ##.#...# #....#G# ######## 1次元化し、現在位置を1値で持てるようにする #########S.#...##..###.###.#...##....#G#########
（上、左、右、下）への移動は、それぞれ $(-W-2, -1, +1, +W+2)$ に対応する。
実装
以下のような入力に対する入力処理例
4 6 ..#... ..###. #.#... ....#.
h, w = map(int, input().split()) h2 = h + 2 w2 = w + 2 grid = '#' * (w2 + 1) + '##'.join(input() for _ in range(h)) + '#' * (w2 + 1)
