矩阵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空间分隔值。接下来的一行包含两个整数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

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