在迷宫中的大鼠中最短路径，可以选择去除一堵墙

Question

这是问题：您有空间站的部分地图，每个地图从监狱出口开始，然后在逃生舱的门口结束。地图表示为0s和1s的矩阵，其中0是可通过的空间，而1则是无法通行的壁。从监狱里走出的门在左上角（0,0），进入逃生舱的门在右下角（W-1，H-1）。

写一个功能答案（地图），该功能从监狱门到逃生舱的最短路径的长度，在那里您可以将一堵墙作为改建计划的一部分拆除。路径长度是您通过的节点总数，同时计数入口和出口节点。起始和结束位置始终可通过（0）。尽管您可能需要或不需要卸下墙壁，但该地图将始终是可以解决的。地图的高度和宽度可以从2到20。只能在基本方向上进行移动；不允许对角线移动。

总结问题：这是一个迷宫问题中的简单大鼠，大鼠在矩阵中的（0,0）开始，应达到（W-1，H-1）。迷宫是0s和1s的矩阵。0表示路径，1表示墙。您有能力去除一个壁（从0更改为1）。找到最短路径。

我已经解决了这个问题，但是5个测试容器中的3个失败了，我不知道这些测试用例是什么。我无法弄清楚原因。提前感谢您的任何帮助。这是我的代码：

import java.util.*;
class Maze{//Each cell in matrix will be this object
Maze(int i,int j){
    this.flag=false;
    this.distance=0;
    this.x=i;
    this.y=j;
}
boolean flag;
int distance;
int x;
int y;
}
class Google4_v2{
public static boolean isPresent(int x,int y,int r,int c)
{
    if((x>=0&&x<r)&&(y>=0&&y<c))
        return true;
    else
        return false;
}
public static int solveMaze(int[][] m,int x,int y,int loop)
{
    int r=m.length;
    int c=m[0].length;
    int result=r*c;
    int min=r*c;
    Maze[][] maze=new Maze[r][c];//Array of objects
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            maze[i][j]=new Maze(i,j);
        }
    }
    Queue<Maze> q=new LinkedList<Maze>();
    Maze start=maze[x][y];
    Maze[][] spare=new Maze[r][c];
    q.add(start);//Adding source to queue
    int i=start.x,j=start.y;
    while(!q.isEmpty())
    {
        Maze temp=q.remove();
        i=temp.x;j=temp.y;
        int d=temp.distance;//distance of a cell from source 
        if(i==r-1 &&j==c-1)
        {
            result=maze[i][j].distance+1;
            break;
        }
        maze[i][j].flag=true;
        if(isPresent(i+1,j,r,c)&&maze[i+1][j].flag!=true)//check down of current cell
        {
            if(m[i+1][j]==0)//if there is path, add it to queue
            {
            maze[i+1][j].distance+=1+d;
            q.add(maze[i+1][j]);
            }
            if(m[i+1][j]==1 && maze[i+1][j].flag==false && loop==0)//if there is no path, see if breaking the wall gives a path.
            {
             int test=solveMaze(m,i+1,j,1);
             if(test>0)
             {
                test+=d+1;
                min=(test<min)?test:min;
             }
             maze[i+1][j].flag=true;
            }
        }
        if(isPresent(i,j+1,r,c)&&maze[i][j+1].flag!=true)//check right of current cell
        {
            if(m[i][j+1]==0)
            {
            maze[i][j+1].distance+=1+d;
            q.add(maze[i][j+1]);
            }
            if(m[i][j+1]==1 && maze[i][j+1].flag==false && loop==0)
            {
             int test=solveMaze(m,i,j+1,1);
             if(test>0)
             {
                test+=d+1;
                min=(test<min)?test:min;
             }
             maze[i][j+1].flag=true;
            }
        }
        if(isPresent(i-1,j,r,c)&&maze[i-1][j].flag!=true)//check up of current cell
        {
            if(m[i-1][j]==0)
            {
            maze[i-1][j].distance+=1+d;
            q.add(maze[i-1][j]);
            }
            if(m[i-1][j]==1 && maze[i-1][j].flag==false && loop==0)
            {
             int test=solveMaze(m,i-1,j,1);
             if(test>0)
             {
                test+=d+1;
                min=(test<min)?test:min;
             }
             maze[i-1][j].flag=true;
            }
        }
        if(isPresent(i,j-1,r,c)&&maze[i][j-1].flag!=true)//check left of current cell
        {
            if(m[i][j-1]==0)
            {
            maze[i][j-1].distance+=1+d;
            q.add(maze[i][j-1]);
            }
            if(m[i][j-1]==1 && maze[i][j-1].flag==false && loop==0)
            {
             int test=solveMaze(m,i,j-1,1);
             if(test>0)
             {
                test+=d+1;
                min=(test<min)?test:min;
             }
             maze[i][j-1].flag=true;
            }
        }
    }
    return ((result<min)?result:min);
}
public static int answer(int[][] m)
{
    int count;
    int r=m.length;
    int c=m[0].length;
    count=solveMaze(m,0,0,0);
    return count;
}
public static void main(String[] args)
{
    Scanner sc=new Scanner(System.in);
    System.out.println("enter row size ");
    int m=sc.nextInt();
    System.out.println("enter column size ");
    int n=sc.nextInt();
    int[][] maze=new int[m][n];
    System.out.println("Please enter values for maze");
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            maze[i][j]=sc.nextInt();
        }
    }
    int d=answer(maze);
    System.out.println("The maze can be solved in "+d+" steps");
}

}

Answer 1

找到了问题。maze[i][j].flag=true;在if(m[i+1][j]==0)条件内访问单元格后需要立即放置。否则，可以通过多个单元格添加同一单元的距离

Answer 2

不幸的是，很难为您提供帮助，因为您的代码很难阅读。变量通常是单个字符，因此无法知道它们应该代表什么。调试这将比我们大多数人愿意提供的更多帮助： - ）

我建议您按以下方式调试代码：

1. 将您的solveMaze方法分为许多较小的方法，这些方法执行了更简单的功能。例如，每个方向都有非常相似的代码重复4次。以一种可以称为4次的方法来获取该代码。将代码移动以将数组创建到新方法中。基本上，每种方法都应该做一件简单的事情。这种方法在出现问题时更容易找到问题。

2. 编写单元测试，以确保这些方法中的每种方法都可以在尝试计算整个迷宫的答案之前确切地完成您的期望。

3. 一旦所有方法正常工作，就会从非常简单的情况到非常复杂的情况开始生成一些迷宫。

4. 案例失败时，请使用交互式调试器浏览您的代码并查看其出错的位置。

祝你好运。