矩阵 n*m 中到目标路径的最短源

Question

给定一个布尔二维矩阵（从 0 开始的索引），找出是否存在从 (0,0) 到 (x,y) 的路径，如果存在一条路径，则打印到达所需的最小步数它，否则如果目的地不可到达则打印-1。你只能在四个方向上移动，即上、下、左、右。如果路径值为 1，则只能从单元格创建路径。

 Example:
    Input:
    2
    3 4
    1 0 0 0 1 1 0 1 0 1 1 1
    2 3
    3 4
    1 1 1 1 0 0 0 1 0 0 0 1
    0 3
    Output:
    5
    3

输入：输入的第一行包含一个整数 T，表示测试用例的数量。然后是 T 个测试用例。每个测试用例包含两行。每个测试用例的第一行包含两个整数 n 和 m，表示矩阵的大小。然后在下一行是矩阵的 n*m space 个分隔值。下一行包含两个整数 x 和 y，表示目的地的索引。

输出：对于每个测试用例，在新行中打印到达目的地所需的最少步数。

代码：

bool isSafe(int currRow,int currCol,int rows,int columns,vector<bool> visited[]) {
    return currRow>=0 && currRow<rows && currCol>=0 && currCol<columns && !visited[currRow][currCol];
}

int minSteps(vector<int> matrix[],int n,int m,int x,int y) {
     vector<bool> visited[n];
     for(int i=0;i<n;i++){
         vector<bool> tmp(m);
         for(int j=0;j<m;j++){
             if(matrix[i][j]==0){
                 tmp[j]=true;
             } else {
                 tmp[j]=false;
             }
         }
         visited[i]=tmp;
     }

     queue<pair<int,int>> q;
     q.push(make_pair(0,0));
     visited[0][0]=true;
     int minDist[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            minDist[i][j]=INT_MAX;
        }
    }
     minDist[0][0]=0;
     static int rows[]={0,1,0,-1};
     static int columns[]={1,0,-1,0};
     while(!q.empty()) {
         pair<int,int> p=q.front();
         q.pop();
         for(int i=0;i<4;i++) {
             if(isSafe(p.first+rows[i],p.second+columns[i],n,m,visited)) {
             visited[p.first+rows[i]][p.second+columns[i]]=true;
               q.push(make_pair(p.first+rows[i],p.second+columns[i]));  
                if(minDist[p.first+rows[i]][p.second+columns[i]]> minDist[p.first][p.second]+1) {
                    minDist[p.first+rows[i]][p.second+columns[i]] = minDist[p.first][p.second]+1;
                } 

             }
         }
     }
     if(minDist[x][y]!=INT_MAX) {
         return minDist[x][y];
     }
     return -1;
}

Test Case Failing
Input:
20 13
0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1
6 3

Its Correct output is:
-1

And Your Code's output is:
13

Algorithm:
1. Traverse the 2 d array from source using  BFS.
2. Maintain 2 2d arrays visited and minDist.
3. Initialize values of visited as true whose value in array is 0 and rest as false; Initialize minDist to INT_MAX.
4. While traversing, validate if its a valid point using isSafen where it is checked if visited is false and point lies within 2d array size limits.
5. If point is safe, make visited for the point as true and push it in the queue.
6. Finlly check if mindist for the point is greater than its parent minDist + 1 ; Update accordingly.

但是我得到了错误的答案；附上失败的测试用例。谁能解释一下我的算法哪里出了问题？

Answer 1

我有遗漏的下角案例：

If matrix[0,0] == 0 
return -1

现在，算法通过了所有测试用例。

矩阵 n*m 中到目标路径的最短源

Shortest Source to Destination Path in a matrix n*m

algorithm

graph

breadth-first-search

shortest-path