差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:grid [2020/07/29] – ikatakos | programming_algorithm:grid [2020/08/06] – ikatakos | ||
|---|---|---|---|
| 行 12: | 行 12: | ||
| ....#G | ....#G | ||
| - | これは、素直に実装すると以下のような課題が発生する。 | + | これは、素直に盤面を2次元配列で実装すると以下のような課題が発生する。 |
| * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | * 一番端のマスから外へ出てはいけないので毎度チェックする必要がある | ||
| * 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する | * 現在位置を $(x,y)$ の2値で持たないといけないので、一度訪れたマスのチェックや、毎回のタプルの生成で計算量が僅かに増加する | ||
| - | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、両方解決する。 | + | いずれも些細な問題と言えばそうだが、以下で紹介されているテクニックを使うと、これらの問題が軽減される。 |
| * [[https:// | * [[https:// | ||
| 行 112: | 行 112: | ||
| </ | </ | ||
| + | |||
| + | |||
| ==== 位置合わせ ==== | ==== 位置合わせ ==== | ||
| 行 136: | 行 138: | ||
| * 「＼」方向は、左上のマスを $(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) | ||
| + | diag = [] | ||
| + | for i in range(si, ti, w - 1): | ||
| + | diag.append(i) | ||
| + | print(diag) | ||
| + | |||
| + | # ↙方向、最右列開始 | ||
| + | for k in range(1, h): | ||
| + | si = w - 1 + k * w | ||
| + | ti = si + min(w, h - k) * (w - 1) | ||
| + | diag = [] | ||
| + | for i in range(si, ti, w - 1): | ||
| + | diag.append(i) | ||
| + | print(diag) | ||
| + | |||
| + | # ↘方向、最上段開始 | ||
| + | for k in range(-w + 1, 1): | ||
| + | si = -k | ||
| + | ti = si + min(h, k + w) * (w + 1) | ||
| + | diag = [] | ||
| + | for i in range(si, ti, w + 1): | ||
| + | diag.append(i) | ||
| + | print(diag) | ||
| + | |||
| + | # ↘方向、最左列開始 | ||
| + | for k in range(1, h): | ||
| + | si = k * w | ||
| + | ti = si + min(w, h - k) * (w + 1) | ||
| + | diag = [] | ||
| + | for i in range(si, ti, w + 1): | ||
| + | diag.append(i) | ||
| + | print(diag) | ||
| + | |||
| + | # [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] | ||
| + | </ | ||
| + | |||
