グリッド

2次元をグリッド上に区切ったマス目を、上下左右、ナナメなど順番に処理することがある。

その際、indexに混乱しないようにメモ。

通行可能なマスと不可能なマスがあり、隣接する上下左右へ移動を繰り返す問題がある。例えば以下の迷路のような問題が代表的。

S.#...
..###.
#.#...
....#G

これは、素直に盤面を2次元配列で実装すると以下のような課題が発生する。

• 一番端のマスから外へ出てはいけないので毎度チェックする必要がある
• 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する

いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、これらの問題が軽減される。

• [AtCoder 参加感想] 2019/01/10:ABC 151 | maspyのHP

全体を壁で覆い、グリッド内かどうかのチェックを壁判定にまとめる
########
#S.#...#
#..###.#
##.#...#
#....#G#
########

1次元化し、現在位置を1値で持てるようにする
#########S.#...##..###.###.#...##....#G#########

（上、左、右、下）への移動は、それぞれ $(-W-2, -1, +1, +W+2)$ に対応する。

以下のような入力に対する入力処理例

4 6
..#...
..###.
#.#...
....#.

グリッドをナナメに辿りたいことがある。

座標の方向を以下のように定める場合、

   →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$）

ナナメ列ごとに、全てのマスを走査する。

ナナメ列同士で比較するときに、そのままだと開始位置が異なるためズレる。これを合わせたい場合、

「＼」方向の列同士の比較は、互いの最も左上のマスを $(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列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、配列の長さを $\max(H,W)$ とした上で、

• 「＼」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$（切り捨て）より開始
• 「／」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W-1}{2}$（切り捨て）より開始

「上下左右への探索」で紹介したのと同様に、1次元で配列を持ちたい場合。

ただし、外壁を作っている場合でも、外壁を含めて全体をイテレートするとする。

統一的に書くのは難しいので、↘方向と↙方向、それぞれ2回に分けて書く。