迷宫最少转弯次数

这题不好做， 不是一般的求最短路径， 而是在所有的出路当中找最少转向次数的一个，这条路径未必就是最短路径。所以，这道题应该用backtrack，而且要记录转向次数，等所有的路径都遍历完了，才能给出最小次数值。

如果动态编程能用的上，那么子问题的最小次数和最后方向都要记录。

孙行者 发表于 2019-4-20 11:31
这题不好做， 不是一般的求最短路径， 而是在所有的出路当中找最少转向次数的一个，这条路径未必就是最短路 ...

如果以转弯的次数当做路径的长度，那么就是BFS吧？转弯一次，代表长度+1

最先访问到终点，那么路径一定是最短的

zdzapple 发表于 2019-4-20 11:53
如果以转弯的次数当做路径的长度，那么就是BFS吧？转弯一次，代表长度+1

最先访问到终点，那么路径一 ...

高明！这一下子就把问题简化了！我咋就没想到呢？

gundamkeroro 发表于 2019-4-19 08:05
leetcode499

这和LC499并不一样。LC499求 lexicographically smallest way，这对于方向有偏好，比如第一步down就比其他任何方向的优先级就更高。
本题就是普通的BFS，解法思想楼上已经有人说了，就是每一步都走到底，然后转弯算作BFS+1. 这个思想对于LC上所有maze系列的题都是通用的。

wisdompeak2 发表于 2019-4-22 01:46
这和LC499并不一样。LC499求 lexicographically smallest way，这对于方向有偏好，比如第一步down就比其 ...

...499不就是普通bfs么

gundamkeroro 发表于 2019-4-22 05:52
...499不就是普通bfs么

哦，我的意思是499求的是lexicographically smallest way。这题求的是最少的拐弯次数。所以说不算是原题。

我只能想到dfs的笨方法

得好好补习一哈bfs

好久不刷都忘了