面试找出最短路径

[Jhonson]

题目描述如图链接

题目大意就是给定一个 n x m 的矩阵，矩阵只含 0 或者 1，其中 0 代表连通，1 代表阻断，给定任意矩阵内两点 A B 坐标，要求找出 A->B 的最短路径（假设是可达的），大家有什么好的思路吗，多多益善，谢谢了。(如果描述不清楚，还请提出。)

Talk is cheap,show your code!

[greenmoon55]

lc 675

[shiyouming91]

BFS+DP，用另一个同样大矩阵保存到达某个点的已知最少的步数，BFS 的每一步检查新矩阵中当前的位置是不是记录了更小或相等的步数。如果是就不再展开这个位置了，否则记录步数到这个位置。空间复杂度是 m*n+BFS 用的栈，我直觉觉得栈肯定比 m*n 小，可以忽略。时间复杂度没分析过，不够一般情况下不会太差。我的直觉是因为 BFS 的初期很容易剪掉相邻的分支，应该是 m*n 或者最多是 m*n*log(m*n)级别的

应该不是最快的解法，不过可扩展性很强，因为很容易处理经过每格格子的开销不一样的情况，以及类似战棋游戏里的移动力有限想知道哪些点是可达的情况，各种涂色的问题等等

总之在十年前之后的硬件条件下我会无脑用这种解法

[p1094358629]

我连题目都看不懂。。。A 为啥是 1，0 按照 XY 坐标不应该是 0，1 吗？？？

[yxcoder]

相对较短其实就算可以的了，最短的收益感觉不大

[yxcoder]

@yxcoder 刚刚发出去就发现理解错误了，尴尬

[yylucifer]

基本算法都不熟悉,还甩:Talk is cheap, show your code!

[Jhonson]

@yylucifer 哈哈哈，这不学着网上的用语的嘛，要是冒犯到你了，我给你道歉~

[takato]

@wannafly 可是不能保证该函数是凸函数呀。

[mbtfdwlx]

如果两点之间权值都是定值 用 BFS 就可以了， 有权值的情况下 就可以考虑 Dijkstra SPFA A-star 都可以

[q397064399]

@Jhonson #47
@yylucifer #46

你还不让人家装个逼过过瘾，大家都是在网上，装一装无所谓的。

[hisune]

https://github.com/hisune/php-astar

[ioth]

学校的题目用来面试，这公司技术了得。

[kzzhr]

都用矩阵存了，这不是 floyd 的标准模板么

[jetyang]

游戏里常用的算法，英雄 A 怎么走可以最快的攻击到英雄 B

[stargazer]

话说想起在爱奇艺面试的时候非让我手写出全部代码。。。。还是自己太渣。。。。

[Jhonson]

@stargazer 你最终写出来了吗那，我当时是说出了利用距离来定夺，但是我只考虑了距离终点的距离，没有考虑起点，还用的是欧氏距离，最终啥都没写出来。

[Jhonson]

@takato 真的没有办法全局最优吗，那只有靠搜索算法来更新的方法最靠谱了呀

[loryyang]

首先想到的就是 BFS 打表，从 A 开始，一直广度搜索打表，更新步长，一直到接触到 B 就结束了

[Solarest]

Floyd 吧

[yuriko]

面试的话，能知道是广搜就行了吧……
就是试探你有没有基本的算法基础……