回答編集履歴
2
リンク先とどのように関連するか追記
test
CHANGED
@@ -2,5 +2,5 @@
|
|
2
2
|
`dest`から`fir`まで、`visited`が減る順番でナイトを動かせば、それが最短経路となります。
|
3
3
|
あとは、たどったところだけ`visited`から`path`に転記すればよいでしょう。
|
4
4
|
|
5
|
-
こちらのリンク先に、単純な迷路における最短経路復元方法の説明があります。私の方法が「方法1」、他の方が説明しているのが「方法2」に対応します。
|
5
|
+
こちらのリンク先に、単純な迷路における最短経路復元方法の説明があります。移動をナイトの動きに変えてあげれば、この問題の解決にも応用できます。なお、私の方法が「方法1」、他の方が説明しているのが「方法2」に対応します。
|
6
6
|
[意外と解説がない!動的計画法で得た最適解を「復元」する一般的な方法](https://qiita.com/drken/items/0c7bab0384438f285f93)
|
1
リンク追加
test
CHANGED
@@ -1,3 +1,6 @@
|
|
1
1
|
一応、今の構造のままでも、最短経路を返すことは可能です。(BFSで見つけた経路と同じとは限りませんが)
|
2
2
|
`dest`から`fir`まで、`visited`が減る順番でナイトを動かせば、それが最短経路となります。
|
3
3
|
あとは、たどったところだけ`visited`から`path`に転記すればよいでしょう。
|
4
|
+
|
5
|
+
こちらのリンク先に、単純な迷路における最短経路復元方法の説明があります。私の方法が「方法1」、他の方が説明しているのが「方法2」に対応します。
|
6
|
+
[意外と解説がない!動的計画法で得た最適解を「復元」する一般的な方法](https://qiita.com/drken/items/0c7bab0384438f285f93)
|