求问一道面试算法题

面Lyft时一道算法题，给弄懵了，求大神解惑！
n*n 的 grid map, 值为0或1, 只有1能通行
现在给定起始点和重点，求最短路径 （假设一定有路径到达）

当时只想到了A*算法，可时间很紧肯定写不完，
面试官让想想更简单方法，可惜没想出来。。。




补充内容 (2019-2-5 06:22):
不好意思，地里新人，此贴可能对大家用处不大，请直接删掉吧

bfs就可以了

飘着的风zk 发表于 2019-2-5 13:36
bfs就可以了

bfs可以很快求出最短步数，
但是维护最短路径节点有啥好方法么?

yangzuyuanhao 发表于 2019-2-6 00:34
bfs可以很快求出最短步数，
但是维护最短路径节点有啥好方法么?

从queue里拿出来只拿出上次的所有步数（bfs已经保证了这是当前最少步数）。所以难道不是用一个int就可以track了么？

补充内容 (2019-2-6 03:43):
看错了问题了。维护最短路径节点，只需要每个节点记住从哪里来的，最后倒着回去就是路径。比如1<-0, 2<-1, 4<-3,9<-1. 结局是9，则9,1,0倒过来即是0,1,9

14417335 发表于 2019-2-6 01:46
从queue里拿出来只拿出上次的所有步数（bfs已经保证了这是当前最少步数）。所以难道不是用一个int就可以t ...

噢对，非常感谢！

14417335 发表于 2019-2-6 01:46
从queue里拿出来只拿出上次的所有步数（bfs已经保证了这是当前最少步数）。所以难道不是用一个int就可以t ...

噢对，非常感谢！