algorithm - 在矩阵中寻找到 X 的路径

Question

给定一个 n x n 矩阵作为输入我们必须找到从 (0,0) 到 X(矩阵中点)是否存在 1 的路径。例如输入是

1 1 1 0 0
1 0 0 0 0 
1 0 X 1 1
1 0 0 0 1
1 1 1 1 1

输出应该是正确的，因为我们有这条路径

1
1
1   X 1 1
1       1
1 1 1 1 1

谁能解释一个更好的方法来做到这一点。谢谢。这是我的算法:

输入矩阵是 A 其中 X 由任何正数表示已访问矩阵 [n][n] 初始化为零初始标志=0；调用 find(0,0,&flag) 然后我们检查 flag=1 是否存在路径。

void find(int i,int j,int * flag)
{

    visited[i][j]=1;

    if(i==n/2)and(j==n/2)
    {
    *flag=1;
     return
    }

    if(A[i+1][j]>0)and(visited[i+1]==0)and(i+1<n)
    find(i+1,j,flag);

    if(A[i-1][j]>0)and(visited[i-1]==0)and(i-1>0)
    find(i-1,j,flag);

    if(A[i][j+1]>0)and(visited[j+1]==0)and(j+1<n)
    find(i,j+1,flag);

    if(A[i][j-1]>0)and(visited[j-1]==0)and(j-1>0)
    find(i,j-1,flag);
}

Answer 1

你的递归算法可能是一个DFS ，它不维护已访问集，因此会多次重新扩展节点。

可以通过添加和维护一个visited集合来解决，如果某个节点在集合中，则跳过它并且不重新扩展它。

更好的选择是使用 BFS而不是 DFS。 BFS 还默认维护一个 visited 集(如果你想稍后找到路径，则为 parent 集)，并且还保证找到从源到目标的最短路径.

BFS 的伪代码:

q = new empty queue
parent = {} //new empty dictionary
q.enqueue((0,0))
parent[(0,0)] = null
while q is not empty:
    current = q.dequeue()
    if current is the target x:
         return findPath(parent, current)
    for each neighbor n of current:
       if n is a key in parent:
          continue
       q.add(n)
       parent[n] = current

findPath(parent, target):
    l = new list
    while (target != null):
       l.add(target)
       target = parent[target]