一道简单的dfs题目,希望大牛帮我解决一下-小明听说在果园里有一个金苹果,他知道金苹果的位子,但是小明很懒,他想知道他最少需要走几步才能摘到金苹果input给出2个整数n(n

Question

一道简单的dfs题目,希望大牛帮我解决一下
-小明听说在果园里有一个金苹果,他知道金苹果的位子,但是小明很懒,他想知道他最少需要走几步才能摘到金苹果
input
给出2个整数n(n

Answer 1

1.这个问题不简单,是经典的算法问题——最短路径问题
2.你的代码改不成对的,至少不是简单改改就行的.因为整体思路就是错的.
3.我不能给你详细的讲解最短路径问题是怎么求解的,只能先指出一个你的错误：如果走进了死胡同,如何回退?怎么保证第一次找到的路就是最短的?
4.建议你找本算法书,看看最短路径问题的求解思路.无非两种:全路径遍历(深度优先)和动态规划（广度优先）.在100×100的复杂度下,可以用全路径遍历.如果迷宫规模扩大到100K*100K,就要用动态规划解决.