差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:grid [2020/08/06] – 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}$（切り捨て）より開始 | ||
| 行 144: | 行 145: | ||
| 「上下左右への探索」で紹介したのと同様に、1次元で配列を持ちたい場合。 | 「上下左右への探索」で紹介したのと同様に、1次元で配列を持ちたい場合。 | ||
| - | ただし、外壁は作っていない（外壁を含めて全体をイテレートする）とする。 | + | ただし、外壁を作っている場合でも、外壁を含めて全体をイテレートするとする。 |
| - | 統一的に書くのは難しいので、↘方向と↙方向、それぞれ2回に分けて書くとする。 | + | 統一的に書くのは難しいので、↘方向と↙方向、それぞれ2回に分けて書く。 |
| <sxh python> | <sxh python> | ||
| 行 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] | ||
| 行 212: | 行 205: | ||
| # [18] | # [18] | ||
| </ | </ | ||
| + | |||
| + | |||
