迷宫最少转弯次数

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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

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

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

maze2 变形

补充内容 (2019-4-19 05:02):
刷题网maze2 变形。。。字数字数字数 ～～～  

leetcode499

面经中没有提及如何变方向。

不过我觉得我们依然可以用相对坐标x,y来去重

BFS，对于当前位置，遍历4个方向，分别一直走到头，加入到下次遍历的队列中。

应该是动态规划吧？

一般求最短路径都是用BFS，这道题leetcode有原题的。

dijkstra求最短路径，而且dijkstra本质是从出发点开始的BFS，所以说成BFS是一样的。

每个转角作为graph的node，转角-转角之间的路作为vector，在这个图上求最短路。

补充内容 (2019-4-19 16:25):
错了。转角-转角之间的路作为node，转角作为带权重的vector。

补充内容 (2019-4-19 16:29):
什么是“要走只能走到头”？只有走到dead end才能换另一条路？那就不适用了。

补充内容 (2019-4-19 16:38):
dijkstra的heap操作貌似是O(log n)的。那确实是BFS好一些

昨天问了一道类似的……这么巧。bfs就行了

sumbo 发表于 2019-4-19 18:37
昨天问了一道类似的……这么巧。bfs就行了

能分享下题目中说的转向吗，是调用他们的函数，类似于robot的turnRight、turnLeft这样子？

还是我们定义个 in[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}} J就行？

我昨天刚刚刷掉了 maze的i - iii 3个题目，在网上找到了一个很详细的题解： http://massivealgorithms.blogspo ... de-499-maze-ii.html




补充内容 (2019-4-20 07:45):
但是我还是有一个地方很困惑 就是maze iii的答案里面，很多时候direction array的定义和平时的正常的定义是相反的。我第一遍写的时候并没有定义成答案的样子。

补充内容 (2019-4-20 07:49):
P.P.S maze ii 的具体解释在网页的第一个链接里 网页是maze iii