文書の過去の版を表示しています。
グリッド
競技プログラミングでは、2次元をグリッド上に区切ったマス目の上で、何かをした結果を求める、という問題がある。
上下左右への探索
通行可能なマスと不可能なマスがあり、隣接する上下左右へ移動を繰り返す問題がある。例えば以下の迷路のような問題が代表的。
S.#... ..###. #.#... ....#G
これは、素直に盤面を2次元配列で実装すると以下のような課題が発生する。
- 一番端のマスから外へ出てはいけないので毎度チェックする必要がある
- 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する
いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、これらの問題が軽減される。
全体を壁で覆い、グリッド内かどうかのチェックを壁判定にまとめる ######## #S.#...# #..###.# ##.#...# #....#G# ######## 1次元化し、現在位置を1値で持てるようにする #########S.#...##..###.###.#...##....#G#########
（上、左、右、下）への移動は、それぞれ $(-W-2, -1, +1, +W+2)$ に対応する。
実装
以下のような入力に対する入力処理例
4 6 ..#... ..###. #.#... ....#.
h, w = map(int, input().split()) grid = '#' * (w + 3) + '##'.join(input() for _ in range(h)) + '#' * (w + 3)
斜めに見る
グリッドをナナメに辿りたいことがある。
座標の方向を以下のように定める場合、
→j 0 1 2 3
i↓ 0 (0,0) (0,1) (0,2) (0,3)
1 (1,0) (1,1) (1,2) (1,3)
2 (2,0) (2,1) (2,2) (2,3)
- 「／」方向のマスは、$i+j$ が一致する
- 「＼」方向のマスは、$i-j$ が一致する
$H \times W$ のグリッドにおいて、
- $i+j$ の取り得る範囲は、$0～H+W-2$
- $i-j$ の取り得る範囲は、$-W+1～H-1$（便宜的に $W-1$ を足すと、$0～H+W-2$）
実装例
ナナメ列ごとに、全てのマスを走査する。
h, w = 4, 5
grid = [list(range(i * w, (i + 1) * w)) for i in range(h)]
for row in grid:
print(row)
# [ 0, 1, 2, 3, 4]
# [ 5, 6, 7, 8, 9]
# [10, 11, 12, 13, 14]
# [15, 16, 17, 18, 19]
# ↙
for ij in range(h + w - 1): # i+j
diag = []
i_min = max(0, ij - w + 1)
i_max = ij - max(0, ij - h + 1)
for i in range(i_min, i_max + 1):
j = ij - i
diag.append(grid[i][j])
print(diag)
# [0]
# [1, 5]
# [2, 6, 10]
# ...
# ↘
for ij in range(-w + 1, h): # i-j
diag = []
i_min = max(0, ij)
i_max = ij + min(w - 1, h - ij - 1)
for i in range(i_min, i_max + 1):
j = i - ij
diag.append(grid[i][j])
print(diag)
# [4]
# [3, 9]
# [2, 8, 14]
# ...
位置合わせ
ナナメ列同士で比較するときに、そのままだと開始位置が異なるためズレる。これを合わせたい場合、
「＼」方向の列同士の比較は、互いの最も左上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1+j_1) - (i_2+j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。
→j 0 1 2 3 4
i↓ 0 □ □ □ ❷ □
1 ❶ □ □ □ ❸ ❷,❸同士を比べたい
2 □ ❷ □ □ □
3 □ □ ❸ □ □
「／」方向の列同士の比較は、互いの最も右上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1-j_1) - (i_2-j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。
→j 0 1 2 3 4
i↓ 0 □ ❷ □ □ □
1 ❸ □ □ □ ❶ ❷,❸同士を比べたい
2 □ □ □ ❷ □
3 □ □ ❸ □ □
2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、
- 「＼」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$（切り捨て）より開始
- 「／」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W-1}{2}$（切り捨て）より開始
