差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
最新のリビジョン両方とも次のリビジョン
programming_algorithm:grid [2020/08/06] – [1次元化] ikatakosprogramming_algorithm:grid [2020/08/12] – [グリッド] ikatakos
行 1: 行 1:
 ====== グリッド ====== ====== グリッド ======
  
-競技プログラミングでは、2次元をグリッド上に区切ったマス目何かをした結果を求めいう問題がある。+2次元をグリッド上に区切ったマス目を、下左右ナナメなど順番に処理すとがある。
  
 +その際、indexに混乱しないようにメモ。
 ===== 上下左右への探索 ===== ===== 上下左右への探索 =====
  
行 161: 行 162:
     si = k     si = k
     ti = si + min(h, k + 1) * (w - 1)     ti = si + min(h, k + 1) * (w - 1)
-    diag = [] 
     for i in range(si, ti, w - 1):     for i in range(si, ti, w - 1):
-        diag.append(i) +        pass
-    print(diag)+
  
 # ↙方向、最右列開始 # ↙方向、最右列開始
行 170: 行 169:
     si = w - 1 + k * w     si = w - 1 + k * w
     ti = si + min(w, h - k) * (w - 1)     ti = si + min(w, h - k) * (w - 1)
-    diag = [] 
     for i in range(si, ti, w - 1):     for i in range(si, ti, w - 1):
-        diag.append(i) +        pass
-    print(diag)+
  
 # ↘方向、最上段開始 # ↘方向、最上段開始
-for k in range(-1, 1): +for k in range(w 1, -1, -1): 
-    si = -+    si = k 
-    ti = si + min(h, k + w) * (w + 1) +    ti = si + min(h, w - k) * (w + 1)
-    diag = []+
     for i in range(si, ti, w + 1):     for i in range(si, ti, w + 1):
-        diag.append(i) +        pass
-    print(diag)+
  
 # ↘方向、最左列開始 # ↘方向、最左列開始
行 188: 行 183:
     si = k * w     si = k * w
     ti = si + min(w, h - k) * (w + 1)     ti = si + min(w, h - k) * (w + 1)
-    diag = [] 
     for i in range(si, ti, w + 1):     for i in range(si, ti, w + 1):
-        diag.append(i) +        pass
-    print(diag)+
  
 # [0] # [0]
行 213: 行 206:
 </sxh> </sxh>
  
- 
-もうちょっとスッキリさせたやつ。min,maxを排除した代わりに割り算を使っているので、速度的には遅いかも。 
- 
-<sxh python> 
-h = 4 
-w = 6 
-grid = list(range(h * w)) 
- 
- 
-def iter_ld(i): 
-    while True: 
-        yield i 
-        d, m = divmod(i, w) 
-        if d == h - 1 or m == 0: 
-            break 
-        i += w - 1 
- 
- 
-def iter_rd(i): 
-    while True: 
-        yield i 
-        d, m = divmod(i, w) 
-        if d == h - 1 or m == w - 1: 
-            break 
-        i += w + 1 
- 
- 
-# ↙方向、最上段開始 
-for k in range(w): 
-    for i in iter_ld(k): 
-        pass 
- 
-# ↙方向、最右列開始 
-for k in range(1, h): 
-    for i in iter_ld(w - 1 + k * w): 
-        pass 
- 
-# ↘方向、最上段開始 
-for k in range(-w + 1, 1): 
-    for i in iter_rd(-k): 
-        pass 
- 
-# ↘方向、最左列開始 
-for k in range(1, h): 
-    for i in iter_rd(k * w): 
-        pass 
-</sxh> 
  
  
programming_algorithm/grid.txt · 最終更新: 2020/08/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0