グリッド

2次元をグリッド上に区切ったマス目の上で、何かを考えることがある。

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

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

これは、そのまま実装すると、以下のような課題が発生する。

• 一番端のマスから外へ出てはいけないので毎度チェックする必要がある
• 現在位置を $(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$
• $i-j$ の取り得る範囲は、$-W～H$ → 便宜的に $W$ を足すと、$0～H+W$ になる

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

「＼」方向の列同士の比較は、互いの最も左上のマスを $(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}{2}$（切り捨て）より開始