c# - 在矩阵中找到最短路径的算法

Question

我试图找到解决以下问题的算法，但找不到。

你有一个矩阵，10X6 如果重要的话。 (x 维度 10，y 维度 6)。该算法接收 2 个点，开放点和目标点。该数组充满了 0 和 1，它应该找到它们之间 1 的最短路径，并返回这条路径中的第一个点(到达目标的下一个点)。但问题是:

每个点只能得到以下点的值:

1. 它上面的那个点。
2. 它下面的点。
3. 留给它的点。
4. 正确的观点。

让事情变得更难的是:对于每一点，其他点的值可能不同。例如:

1. 开点是 0,0。 0,1的值为1；
2. 开点是 0,2。 0,1的值为0。

我可以计算出值(value)，所以这对你来说应该无关紧要......所以我认为解决它的唯一方法是递归，因为最后一个条件，但如果你找到另一种方法，不客气。

解决方案应使用LUA、C# 或JAVA。

Answer 1

您可以简单地将矩阵解释为图形。每个单元格(i,j)对应一个节点v(i,j)，两个节点相连当且仅当它们对应的单元格是邻居且都设置为1时。

下面的示例矩阵有四个顶点 v(0,0)、v(0,1)、v(1,0) 和 v(1,1)，边为 {v(0,0)， v(0,1)} 和 {v(0,1),v(1,1)}(顶点 v(1,0) 是孤立的)。

1 1
0 1

由于您的图表未加权，您可以简单地使用广度优先搜索 (BFS) 来查找最短路径。有关伪代码，请参阅:http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

您对矩阵中的每个条目只知道其相邻条目的限制并不重要。在谈论图时，这意味着每个顶点都知道它的邻居，这正是您在 BFS 中所需要的。从不同的起点搜索时使用不同的图也不会使问题变得更难。

只是对上面链接的 poseudocode 的两条评论:

1. 它只检查是否有连接。如果您真的想要最短路径，则需要更改以下内容。当从它的邻居 t 看到一个新的顶点 u 被添加到队列时，你必须在 u 处存储一个指向 t 的链接。当您最终找到您的目标时，返回链接将为您提供最短路径。

2. 使用集合来存储哪些元素已经被访问过是低效的。在您的情况下，只需使用与输入矩阵大小相同的 bool 矩阵来标记访问的顶点。