主页 / 问题 / 720933
Accepted
kittycat_13
Asked:2020-09-20 22:02:24 +0000 UTC2020-09-20 22:02:24 +0000 UTC

矩阵的深度优先搜索

  • 772

你好。我有一个视图矩阵：

matrix = [
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0]
 ];

我需要找到从起点到终点的路径。您只能在包含 0 的单元格上移动。

var start = [0,4];
 var end = [4,0];

我只能朝四个方向移动。上下左右。方向写在我的数组中。

var direction = [[1,0], [0,1], [-1, 0], [0,-1]];

我有点深入了解搜索算法。但我对运动方向有疑问。这是我的理解：1）将单元格设置为起始坐标。2）开始沿着方向阵列移动单元格。3）如果这个方向不适合我（单元格等于一或单元格不存在，或单元格索引大于矩阵的维度，或小于零），我返回并切换到新的方向。4）如果单元格适合我，我将当前单元格设置为它并再次调用该函数。

但问题是，如何检查相邻单元格是否等于结束值？如果再加一个？

一般来说，我不太了解如何正确实现算法本身。也许我不太了解算法。我会很高兴得到任何帮助。

javascript

1 个回答

  1. Best Answer

    你的 DFS 可能是递归的，所以我会为它做一个例子。对于非递归 DFS，逻辑将类似。

    你说你需要从头到尾。因此，根本不需要检查这个相邻小区是否是最终的。

    做一些不同的事情会更容易：

    1. 我们是否在最后检查，如果是，那么我们完成递归并用这些数据做你需要的事情。如果没有，我们继续。

    2. 我们检查相邻的单元格，如果我们可以进入它们，我们就递归地进入。

    这样，您输入的每个单元格都会被检查。您还可以摆脱不必要的检查。

    • 3

相关问题