差分

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

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:grid [2020/07/31]
ikatakos [上下左右への探索]
programming_algorithm:grid [2020/08/12] (現在)
ikatakos [位置合わせ]
行 1: 行 1:
 ====== グリッド ====== ====== グリッド ======
  
-競技プログラミングでは、2次元をグリッド上に区切ったマス目何かをした結果を求めいう問題がある。+2次元をグリッド上に区切ったマス目を、下左右ナナメなど順番に処理すとがある。
  
 +その際、indexに混乱しないようにメモ。
 ===== 上下左右への探索 ===== ===== 上下左右への探索 =====
  
行 112: 行 113:
  
 </sxh> </sxh>
 +
 +
 ==== 位置合わせ ==== ==== 位置合わせ ====
  
行 132: 行 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-1}{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]
 +</sxh>
 +
 +
 +
programming_algorithm/grid.1596156318.txt.gz · 最終更新: 2020/07/31 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0