差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:grid [2020/08/06] – [1次元化] ikatakos | programming_algorithm:grid [2020/08/12] (現在) – [位置合わせ] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
====== グリッド ====== | ====== グリッド ====== | ||
- | 競技プログラミングでは、2次元をグリッド上に区切ったマス目の上で、何かをした結果を求める、という問題がある。 | + | 2次元をグリッド上に区切ったマス目を、上下左右、ナナメなど順番に処理することがある。 |
+ | その際、indexに混乱しないようにメモ。 | ||
===== 上下左右への探索 ===== | ===== 上下左右への探索 ===== | ||
行 134: | 行 135: | ||
3 □ □ ❸ □ □ | 3 □ □ ❸ □ □ | ||
- | 2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、 | + | 2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、配列の長さを $\max(H,W)$ とした上で、 |
* 「\」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$(切り捨て)より開始 | * 「\」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$(切り捨て)より開始 | ||
行 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): | ||
- | | + | |
- | 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): | ||
- | | + | |
- | print(diag) | + | |
# ↘方向、最上段開始 | # ↘方向、最上段開始 | ||
- | for k in range(-w + 1, 1): | + | for k in range(w |
- | si = -k | + | si = k |
- | ti = si + min(h, k + w) * (w + 1) | + | ti = si + min(h, |
- | diag = [] | + | |
for i in range(si, ti, w + 1): | for i in range(si, ti, w + 1): | ||
- | | + | |
- | 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): | ||
- | | + | |
- | print(diag) | + | |
# [0] | # [0] | ||
行 213: | 行 206: | ||
</ | </ | ||
- | |||
- | もうちょっとスッキリさせたやつ。min, | ||
- | |||
- | <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 | ||
- | </ | ||