dfs和bfs算法的区别 走格子路线算法？

走格子路线算法？

给定一个二维数组，找出是否有从左上角到右下角的路径。在给定的二维数组中，当单元格值为-1时，表示不能通过；当单元格值为0时，表示可以通过。

例如：给定如下二维数组：

{0，0，0，-1，0}，

{1，0，0，-1，-1}，]{0，0，-1，0}，

{1，0，0，0，0}，

{0，0，-1，0}]路径存在，返回yes

{0，0，0，-1，0}，

{1，0，0，-1}，

{0，0，-1，0}，

{1，0，-1，0}，

{，0}

路径不存在，返回no

算法分析

解决此问题的简单方法是使用BFS或DFS算法来查找是否有一条合格的路径（path）。

更好的解决方案是通过将所有可访问节点的值更改为1来标记它们。

首先，将左上角第一个元素的值标记为1。然后获取第一行中的下一个（当前）值，并将其与上一个值进行比较。仅当当前值可到达（不等于-1）时，才将其设置为上一个值。类似地，对列值执行相同的操作，方法是将当前值与前一列的值（如果可以访问）进行比较并进行设置。

然后从第一行和第一列开始，获取前一行和前一列的值。找到它们之间的最大值，并将当前索引设置为该最大值。如果当前索引值为-1，则没有更改。

最后，如果右下角的最终索引为1，则返回“是”，否则返回“否”。

dfs和bfs算法的区别 dfs算法原理 dfs算法经典应用

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。