差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:grid [2020/07/29] – 作成 ikatakos
+++ programming_algorithm:grid [2020/07/29] – [位置合わせ] ikatakos
@@ 行 17: / 行 17: @@
   * 現在位置を $(x,y)$ の2値で持たないといけないので、計算量が僅かに増加する
-いずれも些細な問題と言えばそうだが、以下に示すテクニックを使うと、両方解決する。
+いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。
   * [[https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-01-10abc-151|[AtCoder 参加感想] 2019/01/10:ABC 151 | maspyのHP]]
@@ 行 46: / 行 46: @@
 <sxh python>
 h, w = map(int, input().split())
-h2 = h + 2
+grid = '#' * (w + 3) + '##'.join(input() for _ in range(h)) + '#' * (w + 3)
-w2 = w + 2
-grid = '#' * (w2 + 1) + '##'.join(input() for _ in range(h)) + '#' * (w2 + 1)
 </sxh>
+===== 斜めに見る =====
+グリッドをナナメに辿りたいことがある。
+座標の方向を以下のように定める場合、
+     →j   0     1     2     3
+  i↓ 0 (0,0) (0,1) (0,2) (0,3)
+(1,0) (1,1) (1,2) (1,3)
+(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$）
+==== 実装例 ====
+ナナメ列ごとに、全てのマスを走査する。
+<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, i_max + 1):
+        j = ij - i
+        diag.append(grid[i][j])
+    print(diag)
+# [0]
+# [1, 5]
+# [2, 6, 10]
+# ...
+# ↘
+for ij in range(h + w - 1):  # i-j+W-1
+    ij -= w - 1
+    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]
+# ...
+</sxh>
+==== 位置合わせ ====
+ナナメ列同士で比較するときに、そのままだと開始位置が異なるためズレる。これを合わせたい場合、
+「＼」方向の列同士の比較は、互いの最も左上のマスを $(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 □ □ □ ❷ □
+❶ □ □ □ ❸    ❷,❸同士を比べたい
+□ ❷ □ □ □
+□ □ ❸ □ □
+「／」方向の列同士の比較は、互いの最も右上のマスを $(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 □ ❷ □ □ □
+❸ □ □ □ ❶    ❷,❸同士を比べたい
+□ □ □ ❷ □
+□ □ ❸ □ □
+つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、
+  * 「＼」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$（切り捨て）より開始
+  * 「／」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W-1}{2}$（切り捨て）より開始