这是一个创建于 2835 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目大意就是给定一个 n x m 的矩阵，矩阵只含 0 或者 1，其中 0 代表连通，1 代表阻断，给定任意矩阵内两点 A B 坐标，要求找出 A->B 的最短路径（假设是可达的），大家有什么好的思路吗，多多益善，谢谢了。(如果描述不清楚，还请提出。)
Talk is cheap,show your code!
 | 1 classyk 2018 年 6 月 27 日 via iPhone 这个不就是 Astar 算法吗 |
 | 2 baiihcy 2018 年 6 月 27 日 BFS 就能实现了吧 |
 | 5 LawlietZ 2018 年 6 月 27 日 via iPad 裸 dijksta 啊 超级简单。。。哪个公司的面试啊。。。 |
 | 8 cbais7890 2018 年 6 月 27 日  9 |
 | 11 Parallel 2018 年 6 月 27 日 2 题目描述的表示图的方式叫，邻接矩阵。针对这个题目，对应不同的查询需求，可以扯的有很多。 以下，n 为顶点数，e 为边数。 O(n^3) Floyd O(n^2) Dijkstra O(n*e) Bellman-ford O(e) SPFA |
 | 12 ballshapesdsd 2018 年 6 月 27 日 你们都审题了没有啊，怎么迪杰斯特拉都出来了 |
| @ballshapesdsd 哦，点开链接才看到完整的题目，理解题目有误。 |
 | 16 takato 2018 年 6 月 27 日 @ballshapesdsd 似乎好多人理解成了邻接矩阵。。。 其实是张迷宫图。。。 |
 | 18 HiJ2017 2018 年 6 月 27 日 这是很经典的数据结构题,当时教材上给了 BFS 和 DFS 两种解法 <数据结构教程>--李春葆 |
 | 21 silhouette 2018 年 6 月 27 日 via Android floyd，模板题 |
 | 24 wizardforcel 2018 年 6 月 27 日 floyd 有点浪费了，它最后就要 distance[A][B] |
| 25 takato 2018 年 6 月 27 日 @wannafly 问题是如果退化了以后，状态数还是和 DFS,BFS 一样，那么这个 function 在这个例子中的意义在哪里？ 当然我可以理解想做一个 Universal Algorithm/Model 的决心，但是也别忘了 overfit 的存在。 即如果只是要个 local minimum，你说的就是比较好的方法，但是源问题不是这样定义的。 |
 | 26 JohnSmith 2018 年 6 月 27 日 via Android 动规问题 刚做过 |
 | 28 IceCola1 2018 年 6 月 27 日 对于的矩阵转换为图，如果只是 0，1 的话，深搜或者广搜都可以，时间复杂度都是 OV2,如果有权重的话，用 Dijkstra,时间复杂度，OV2，如果有负权重的话，bellman-ford 算法 O(VE)，如果所有点对都要输出的话，floyd 算法 O(V3) |
 | 29 Rico 2018 年 6 月 27 日 可以参考我之前写的 A*算法，有动图 https://hogwartsrico.github.io/2016/03/11/AStarPathFinding/ |
 | 30 lsmgeb89 2018 年 6 月 28 日 bfs |
 | 32 Mirana 2018 年 6 月 28 日 dp |
 | 33 jedihy 2018 年 6 月 28 日 这种题目就真的不 show code 了，BFS 送分题。 |
 | 35 wolegequ 2018 年 6 月 28 日 via Android 还 talk is cheap |
 | 36 jssyxzy 2018 年 6 月 28 日 算法自己复习。 |
 | 37 laxenade 2018 年 6 月 28 日 leetcode 64 的变种？ |
 | 38 trn4 2018 年 6 月 28 日 这种路径长度都相同的题，用不着 dijkstra，单纯的 BFS。另外面试一般不会考 Floyd 吧…… |
 | 39 thedrwu 2018 年 6 月 28 日 看需要查询几次。 是否需要“最”优解。 如果只考虑短时间内能简单实现的解法： 若查询一次可以如楼上用广搜。 若查询多次，整张 n×m 表一遍一遍的扫（递推），假设点 a->点 z, 每扫一遍更新上一的解(a->b->z 中的 b)和最优路径和数， 直到收敛。 空间只需要 O(n×m)。 |
 | 40 wannafly 2018 年 6 月 28 日 via Android @takato 只要能保证 heuristic cost 算出来小于等于实际的 cost，那么就能保证得到的解是全局最优解。这种情况下也是能减少所要搜索的状态数量的。 |
 | 41 greenmoon55 2018 年 6 月 28 日 lc 675 |
 | 42 shiyouming91 2018 年 6 月 28 日 BFS+DP，用另一个同样大矩阵保存到达某个点的已知最少的步数，BFS 的每一步检查新矩阵中当前的位置是不是记录了更小或相等的步数。如果是就不再展开这个位置了，否则记录步数到这个位置。空间复杂度是 m*n+BFS 用的栈，我直觉觉得栈肯定比 m*n 小，可以忽略。时间复杂度没分析过，不够一般情况下不会太差。我的直觉是因为 BFS 的初期很容易剪掉相邻的分支，应该是 m*n 或者最多是 m*n*log(m*n)级别的 应该不是最快的解法，不过可扩展性很强，因为很容易处理经过每格格子的开销不一样的情况，以及类似战棋游戏里的移动力有限想知道哪些点是可达的情况，各种涂色的问题等等 总之在十年前之后的硬件条件下我会无脑用这种解法 |
 | 43 p1094358629 2018 年 6 月 28 日 我连题目都看不懂。。。A 为啥是 1，0 按照 XY 坐标不应该是 0，1 吗？？？ |
 | 44 yxcoder 2018 年 6 月 28 日 相对较短其实就算可以的了，最短的收益感觉不大 |
 | 46 yylucifer 2018 年 6 月 28 日 基本算法都不熟悉,还甩:Talk is cheap, show your code! |
 | 49 IceSolStice 2018 年 6 月 28 日 如果两点之间权值都是定值 用 BFS 就可以了， 有权值的情况下 就可以考虑 Dijkstra SPFA A-star 都可以 |
 | 50 q397064399 2018 年 6 月 28 日 |
 | 51 hisune 2018 年 6 月 28 日 |
 | 52 ioth 2018 年 6 月 28 日 学校的题目用来面试，这公司技术了得。 |
 | 53 kzzhr 2018 年 6 月 28 日 via Android 都用矩阵存了，这不是 floyd 的标准模板么 |
 | 54 jetyang 2018 年 6 月 28 日 游戏里常用的算法，英雄 A 怎么走可以最快的攻击到英雄 B |
 | 55 stargazer 2018 年 6 月 28 日 话说想起在爱奇艺面试的时候非让我手写出全部代码。。。。还是自己太渣。。。。 |
 | 56 Jhonson OP @stargazer 你最终写出来了吗那，我当时是说出了利用距离来定夺，但是我只考虑了距离终点的距离，没有考虑起点，还用的是欧氏距离，最终啥都没写出来。 |
 | 58 loryyang 2018 年 6 月 28 日 首先想到的就是 BFS 打表，从 A 开始，一直广度搜索打表，更新步长，一直到接触到 B 就结束了 |
 | 59 Solarest 2018 年 6 月 28 日 Floyd 吧 |
 | 60 yuriko 2018 年 6 月 28 日 面试的话，能知道是广搜就行了吧…… 就是试探你有没有基本的算法基础…… |
 | 62 zzj0311 2018 年 6 月 28 日 via Android 就是个 A*，哪那么多问题。。 |
 | 64 lzhCoooder 2018 年 6 月 28 日 dijksta 和 A*都可以啊，选哪个看实际情况，面试的话把这两个算法都说出来没毛病 |
 | 65 salamanderMH 2018 年 6 月 28 日 |
 | 66 yao978318542 2018 年 6 月 28 日 |
 | 67 mogami18 2018 年 6 月 28 日 floyd |
 | 68 zke1e 2018 年 6 月 28 日 dijkstra 啊 |
 | 69 maggch 2018 年 6 月 28 日 这题边权都是 1,最优就是 BFS 了 |
| 70 maggch 2018 年 6 月 28 日 Dijkstra 带 log ,Floyd 复杂度 n^3,做这题时间复杂度都非常的不优秀 |
Select Language