回答編集履歴
1
座標による詰み
answer
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
### 総当たり
|
|
2
|
+
|
|
1
3
|
総当たりでもいいと思いますが、
|
|
2
4
|
|
|
3
5
|
1. 二次元座標マップ(二次元配列)として変数 map を作り、全要素値を false にする。要素値は通過フラグである(通過済 = true, 未通過 =false)。
|
|
@@ -7,6 +9,8 @@
|
|
|
7
9
|
5. 移動座標の map 値が true なら 4. へ戻る。座標が false なら true に変更し、変数 x, y を初期化
|
|
8
10
|
6. 5. で3回 4. へ戻る動作が発生したら終了
|
|
9
11
|
|
|
12
|
+
### 三手先をシミュレーション
|
|
13
|
+
|
|
10
14
|
三手先をシミュレーションすると、直前の二手によって、移動先の「左上」「下」「右」の中で**移動できない選択肢**がある事に気が付きます。
|
|
11
15
|
|
|
12
16
|
- なぜ移動できないのか
|
|
@@ -14,4 +18,21 @@
|
|
|
14
18
|
|
|
15
19
|
上記を論理的に考え、アルゴリズムに落とし込むだけでも最適化は可能だと思います。
|
|
16
20
|
|
|
21
|
+
> 2手前の移動方向と1手前の移動方向が異なる時,この2つに使われていない移動方向に移動することが出来ないですね(すでに訪問済みであるため)。
|
|
22
|
+
|
|
23
|
+
そうですね。
|
|
24
|
+
|
|
25
|
+
- 直前のニ手を変数で持っておく
|
|
26
|
+
- 移動可能な方向を変数で持っておく `['left-up', 'right', 'down']`
|
|
27
|
+
|
|
28
|
+
このようにすれば、変数値を変更する事で移動可能な方向を制御出来ます。
|
|
29
|
+
|
|
30
|
+
### 座標による詰み
|
|
31
|
+
|
|
32
|
+
例えば、上から3行目の左端から右端まで、右方向に移動し続けたとします。
|
|
33
|
+
次に「左上」に移動すれば、3行目より下に行けなくなり、「下」に移動すれば、3行目より上に行けなくなります。
|
|
34
|
+
つまり、同一行で全ての列が通過済の状況になると、上下のどちらかの全座標が通過済でない限りは詰みます。
|
|
35
|
+
各行の通過済の列数を記録しておけば、このような事態は防げます。
|
|
36
|
+
列に関しても、同様ですね。
|
|
37
|
+
|
|
17
38
|
Re: okamot さん
|