差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:grid [2020/07/29] – [斜めに見る] ikatakos | programming_algorithm:grid [2020/08/12] (現在) – [位置合わせ] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
====== グリッド ====== | ====== グリッド ====== | ||
- | 2次元をグリッド上に区切ったマス目の上で、何かを考えることがある。 | + | 2次元をグリッド上に区切ったマス目を、上下左右、ナナメなど順番に処理することがある。 |
+ | その際、indexに混乱しないようにメモ。 | ||
===== 上下左右への探索 ===== | ===== 上下左右への探索 ===== | ||
行 12: | 行 13: | ||
....#G | ....#G | ||
- | これは、そのまま実装すると、以下のような課題が発生する。 | + | これは、素直に盤面を2次元配列で実装すると以下のような課題が発生する。 |
* 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | ||
- | * 現在位置を $(x,y)$ の2値で持たないといけないので、計算量が僅かに増加する | + | * 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する |
- | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | + | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、これらの問題が軽減される。 |
* [[https:// | * [[https:// | ||
- | 全体を壁で覆い、グリッド内かどうかのチェックを不要にする | + | 全体を壁で覆い、グリッド内かどうかのチェックを壁判定にまとめる |
######## | ######## | ||
#S.#...# | #S.#...# | ||
行 65: | 行 66: | ||
$H \times W$ のグリッドにおいて、 | $H \times W$ のグリッドにおいて、 | ||
- | * $i+j$ の取り得る範囲は、$0~H+W$ | + | * $i+j$ の取り得る範囲は、$0~H+W-2$ |
- | * $i-j$ の取り得る範囲は、$-W~H$ | + | * $i-j$ の取り得る範囲は、$-W+1~H-1$(便宜的に $W-1$ を足すと、$0~H+W-2$) |
+ | |||
+ | ==== 実装例 ==== | ||
+ | |||
+ | ナナメ列ごとに、全てのマスを走査する。 | ||
+ | |||
+ | <sxh python> | ||
+ | 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, | ||
+ | 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, | ||
+ | j = i - ij | ||
+ | diag.append(grid[i][j]) | ||
+ | print(diag) | ||
+ | # [4] | ||
+ | # [3, 9] | ||
+ | # [2, 8, 14] | ||
+ | # ... | ||
+ | |||
+ | </ | ||
==== 位置合わせ ==== | ==== 位置合わせ ==== | ||
行 88: | 行 135: | ||
3 □ □ ❸ □ □ | 3 □ □ ❸ □ □ | ||
- | 2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、 | + | 2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、配列の長さを $\max(H,W)$ とした上で、 |
* 「\」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$(切り捨て)より開始 | * 「\」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$(切り捨て)より開始 | ||
- | * 「/」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W}{2}$(切り捨て)より開始 | + | * 「/」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W-1}{2}$(切り捨て)より開始 |
+ | |||
+ | |||
+ | ==== 1次元化 ==== | ||
+ | |||
+ | 「上下左右への探索」で紹介したのと同様に、1次元で配列を持ちたい場合。 | ||
+ | |||
+ | ただし、外壁を作っている場合でも、外壁を含めて全体をイテレートするとする。 | ||
+ | |||
+ | 統一的に書くのは難しいので、↘方向と↙方向、それぞれ2回に分けて書く。 | ||
+ | |||
+ | <sxh python> | ||
+ | h = 4 | ||
+ | w = 6 | ||
+ | grid = list(range(h * w)) | ||
+ | # 0 1 2 3 4 5 | ||
+ | # 6 7 8 9 10 11 | ||
+ | # 12 13 14 15 16 17 | ||
+ | # 18 19 20 21 22 23 | ||
+ | |||
+ | # ↙方向、最上段開始 | ||
+ | for k in range(w): | ||
+ | si = k | ||
+ | ti = si + min(h, k + 1) * (w - 1) | ||
+ | for i in range(si, ti, w - 1): | ||
+ | pass | ||
+ | |||
+ | # ↙方向、最右列開始 | ||
+ | for k in range(1, h): | ||
+ | si = w - 1 + k * w | ||
+ | ti = si + min(w, h - k) * (w - 1) | ||
+ | for i in range(si, ti, w - 1): | ||
+ | pass | ||
+ | |||
+ | # ↘方向、最上段開始 | ||
+ | for k in range(w - 1, -1, -1): | ||
+ | si = k | ||
+ | ti = si + min(h, w - k) * (w + 1) | ||
+ | for i in range(si, ti, w + 1): | ||
+ | pass | ||
+ | |||
+ | # ↘方向、最左列開始 | ||
+ | for k in range(1, h): | ||
+ | si = k * w | ||
+ | ti = si + min(w, h - k) * (w + 1) | ||
+ | for i in range(si, ti, w + 1): | ||
+ | pass | ||
+ | |||
+ | # [0] | ||
+ | # [1, 6] | ||
+ | # [2, 7, 12] | ||
+ | # [3, 8, 13, 18] | ||
+ | # [4, 9, 14, 19] | ||
+ | # [5, 10, 15, 20] | ||
+ | # [11, 16, 21] | ||
+ | # [17, 22] | ||
+ | # [23] | ||
+ | # [5] | ||
+ | # [4, 11] | ||
+ | # [3, 10, 17] | ||
+ | # [2, 9, 16, 23] | ||
+ | # [1, 8, 15, 22] | ||
+ | # [0, 7, 14, 21] | ||
+ | # [6, 13, 20] | ||
+ | # [12, 19] | ||
+ | # [18] | ||
+ | </ | ||
+ | |||
+ |