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

给定一个布尔2D矩阵(基于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.

但是我得到了错误的答案。附加失败的测试用例。有人可以解释我的算法出了什么问题吗?

评论