algorithm - 在8个方向上遍历矩阵迷宫

给您一个1和0的矩阵，其中0表示空闲路径，1表示阻塞区域你可以朝八个方向中的任何一个移动。查找从源到目标的最短路径。
我想出了一个解决方案，其中dp[i,j]存储到起始顶点的最小距离：

recursion(int i, int j , int sum)
{

  if(!issafe(i,j) || isvisited[i,j]) // within bounds
  return ;

  if(matrix(i,j)==0)//blocked
  return ;

  isvisited[i,j]=true;

  dp[i,j] = min(dp[i,j] , sum);
  // directions have usual meaning

  recursion(east ,sum+1);  // i , j+1
  recursion(north , sum+1);  //i-1 , j
  recursion(west , sum+1);
  recursion(south , sum+1);
  recursion(north-east , sum+1);
  recursion(north-west , sum+1);
  recursion(south-east , sum+1);
  recursion(south-west , sum+1);

  isvisited[i,j]=false;

return;
}

现在我怀疑的是，假设我们能从8个位置到达[i，j]一旦我从位置1到达它，比如说最小路径是x个单位，我就立即递归地检查它的邻居现在，我从路径2找到min.path（以前的x）现在是y而不是x，然后再次递归检查。所以，我在步骤1做了额外的计算，这是不需要的在当前单元格中找到最小路径（从所有8个位置都可以到达）后，是否有方法递归检查邻居？

最佳答案

这是非加权图中的ashortest path problem，可由aBFS求解。
在这里你的图表是
G=(V,E)
V = { all cells in the matrix}
注意，您的方法是DFS的变体，使用附加数据[theE= { (v1,v2) | can move from cell v1 to cell v2 }数组]
更先进的方法是bi-directional搜索或A* algorithm（以manhattan distances作为启发式函数）。
bfs伪码：

BFS(source,destination):
  visited <- {} //empty dictionary
  queue <- new queue
  queue.add (source)
  visited.add(source,null)
  while (! queue.isEmpty()):
      v <- queue.pop()
      if v == destination:
         return getPath(visited, v)
      for each edge (v,u):
         if u is not a key in visited:
             visited.add(u,v)
             queue.add(u)

getPath(visited,v):
   list <- new linked list
   while (v != null):
      list.addFirst(v)
      v <- visited.get(v)
   return list

该解的时间复杂度为dp，其中O(min{|V|,8^d})为最短路径长度，d为矩阵中的单元数。