差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:grid [2020/07/29] – [上下左右への探索] ikatakos | programming_algorithm:grid [2020/07/29] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== グリッド ====== | ====== グリッド ====== | ||
| - | 2次元をグリッド上に区切ったマス目の上で、何かを考えることがある。 | + | 競技プログラミングでは、2次元をグリッド上に区切ったマス目の上で、何かをした結果を求める、という問題がある。 |
| ===== 上下左右への探索 ===== | ===== 上下左右への探索 ===== | ||
| 行 12: | 行 12: | ||
| ....#G | ....#G | ||
| - | これは、そのまま実装すると、以下のような課題が発生する。 | + | これは、素直に実装すると以下のような課題が発生する。 |
| * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | ||
| - | * 現在位置を $(x,y)$ の2値で持たないといけないので、計算量が僅かに増加する | + | * 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する |
| いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | ||
| 行 21: | 行 21: | ||
| * [[https:// | * [[https:// | ||
| - | 全体を壁で覆い、グリッド内かどうかのチェックを不要にする | + | 全体を壁で覆い、グリッド内かどうかのチェックを壁判定にまとめる |
| ######## | ######## | ||
| #S.#...# | #S.#...# | ||
| 行 65: | 行 65: | ||
| $H \times W$ のグリッドにおいて、 | $H \times W$ のグリッドにおいて、 | ||
| - | * $i+j$ の取り得る範囲は、$0～H+W$ | + | * $i+j$ の取り得る範囲は、$0～H+W-2$ |
| - | * $i-j$ の取り得る範囲は、$-W～H$ | + | * $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, | ||
| + | j = ij - i | ||
| + | diag.append(grid[i][j]) | ||
| + | print(diag) | ||
| + | # [0] | ||
| + | # [1, 5] | ||
| + | # [2, 6, 10] | ||
| + | # ... | ||
| + | |||
| + | # ↘ | ||
| + | for ij in range(-w + 1, h): # i-j | ||
| + | diag = [] | ||
| + | i_min = max(0, ij) | ||
| + | i_max = ij + min(w - 1, h - ij - 1) | ||
| + | for i in range(i_min, | ||
| + | j = i - ij | ||
| + | diag.append(grid[i][j]) | ||
| + | print(diag) | ||
| + | # [4] | ||
| + | # [3, 9] | ||
| + | # [2, 8, 14] | ||
| + | # ... | ||
| + | |||
| + | </ | ||
| + | ==== 位置合わせ ==== | ||
| ナナメ列同士で比較するときに、そのままだと開始位置が異なるためズレる。これを合わせたい場合、 | ナナメ列同士で比較するときに、そのままだと開始位置が異なるためズレる。これを合わせたい場合、 | ||
| + | |||
| + | 「＼」方向の列同士の比較は、互いの最も左上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1+j_1) - (i_2+j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。 | ||
| →j 0 1 2 3 4 | →j 0 1 2 3 4 | ||
| 行 76: | 行 124: | ||
| 3 □ □ ❸ □ □ | 3 □ □ ❸ □ □ | ||
| - | 「＼」方向の列同士の比較は、互いの最も左上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1+j_1) - (i_2+j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。 | + | 「／」方向の列同士の比較は、互いの最も右上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1-j_1) - (i_2-j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。 |
| →j 0 1 2 3 4 | →j 0 1 2 3 4 | ||
| 行 84: | 行 132: | ||
| 3 □ □ ❸ □ □ | 3 □ □ ❸ □ □ | ||
| - | 「／」方向の列同士の比較は、互いの最も右上のマスを $(i_1,j_1), (i_2,j_2)$ とすると、$\dfrac{|(i_1-j_1) - (i_2-j_2)|}{2}$ だけ、大きい方を後ろにずらせばよい。 | + | 2つずつの比較でなく、任意の2列を比較できるよう全体として共通のオフセットを持たせておきたい場合は、 |
| + | * 「＼」方向は、左上のマスを $(i,j)$ とすると、indexは $\dfrac{i+j}{2}$（切り捨て）より開始 | ||
| + | * 「／」方向は、右上のマスを $(i,j)$ とすると、indexは $\dfrac{i-j+W-1}{2}$（切り捨て）より開始 | ||
