java - 通过检查点找到穿过迷宫的最小路径

Question

我正在尝试找到从起点“S”到目标“G”通过所有检查点“@”的最小路径。虽然我听说最佳优先搜索很有效，但我使用了使用队列的广度优先搜索。我正在为每个点的每个可能路径创建新的 Mazestate 对象并将其添加到队列中。但是，当我更改队列中一个对象中某个位置的值时，所有其他对象中的值也会更改(至少这是我认为正在发生的情况)。

请告诉我哪里出错了。我认为“maze1”或“temp.maze2”有问题

抱歉，代码很破旧。

class ortry1
{
    static int w,h;
    static int sx,sy,gx,gy;
    static int anos=0;
    public static char[][] maze3=null;
    static boolean goalfound=false;
    static Queue<Mazestate> statequeue=new LinkedList<>();
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        Scanner scan=new Scanner(System.in);
        w=(int)scan.nextInt();
        h=(int)scan.nextInt();
        maze3=new char[h][w];
        String tempo=null;
        for(int i=0;i<h;i++)
        {
            tempo=br.readLine();
            maze3[i]=tempo.toCharArray();
            if(tempo.indexOf('S')!=-1)
            {
                sx=i;sy=tempo.indexOf('S');
            }
            if(tempo.indexOf('G')!=-1)
            {
                gx=i;gy=tempo.indexOf('G');
            }           
                for(int k=0;k<w;k++)
                {
                    if(maze3[i][k]=='@')
                    {
                        anos++;
                    }
                }
        }

    statequeue.add(new Mazestate(maze3,sx, sy, 0, 0));
    ortry1 o=new ortry1();
    while(!goalfound)
    {
        o.populatequeue();
    }

    }
private void populatequeue() 
{
    if (statequeue.peek()!=null)
    {
        Mazestate temp=statequeue.poll();
        char[][] maze1=temp.maze2.clone();
        int curx=temp.curx;
        int cury=temp.cury;
        int atscrossed=temp.atscrossed;
        int stepcount=temp.stepcount;
        System.out.println(atscrossed+"    "+stepcount);

        if(maze1[curx][cury]=='.'){maze1[curx][cury]='1';}
        else if(maze1[curx][cury]=='1'){maze1[curx][cury]='2';}
        else if(maze1[curx][cury]=='2'){maze1[curx][cury]='3';}
        else if(maze1[curx][cury]=='3'){maze1[curx][cury]='4';}
        else if(maze1[curx][cury]=='@'){maze1[curx][cury]='1';}
        else if(maze1[curx][cury]=='S'){maze1[curx][cury]='1';}



        for(int y=0;y<h;y++){System.out.println();
        for(int z=0;z<w;z++)
        {System.out.print(maze1[y][z]+"   ");}}


        //------------UP[curx-1][cury]--------------

        if(((curx-1)>=0)&&(maze1[curx-1][cury]!='#')&&(maze1[curx-1][cury]!='4'))
        {
            System.out.print("up        ");
            if((maze1[curx-1][cury]=='G'))
            {
                System.out.println("inG");
                if(atscrossed==ortry1.anos)
                {
                    goalfound=true;
                    System.out.println("===="+(stepcount+1));
                }else
                {
                    statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed, stepcount+1));
                }
            }else if(maze1[curx-1][cury]=='@')
            {
                System.out.print("in@");            
                statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed+1, stepcount+1));
            }else if(maze1[curx-1][cury]=='.')
            {
                System.out.println("in.");          
                statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed, stepcount+1));

            }else if(maze1[curx-1][cury]=='1')
            {
                System.out.println("in1");              
                statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed, stepcount+1));
            }else if(maze1[curx-1][cury]=='2')
            {
                System.out.println("in2");              
                statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed, stepcount+1));
            }else if(maze1[curx-1][cury]=='3')
            {
                System.out.println("in3");
                statequeue.add(new Mazestate(maze1,curx-1, cury, atscrossed, stepcount+1));
            }
            maze1=temp.maze2.clone();
        }
        //-----------DOWN[curx+1][cury]------------
        if(((curx+1)<ortry1.h)&&(maze1[curx+1][cury]!='#')&&(maze1[curx+1][cury]!='4'))
        {
            System.out.print("down      ");
            if((maze1[curx+1][cury]=='G'))
            {
                System.out.println("inG");
                if(atscrossed==ortry1.anos)
                {
                    goalfound=true;
                    System.out.println("===="+(stepcount+1));
                }else
                {
                    statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed, stepcount+1));
                }
            }else   if(maze1[curx+1][cury]=='@')
            {
                System.out.println("in@");  
                statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed+1, stepcount+1));
            }else if(maze1[curx+1][cury]=='.')
            {
                System.out.println("in.");  
                statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed, stepcount+1));
            }

            else if(maze1[curx+1][cury]=='1')
            {
                System.out.println("in1");  
                statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed, stepcount+1));
            }else if(maze1[curx+1][cury]=='2')
            {
                System.out.println("in2");
                statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed, stepcount+1));
            }else if(maze1[curx+1][cury]=='3')
            {
                System.out.println("in3");
                statequeue.add(new Mazestate(maze1,curx+1, cury, atscrossed, stepcount+1));
            }

        maze1=temp.maze2.clone();
        }

        //------------LEFT[curx][cury-1]-----------------
        if(((cury-1)>=0)&&(maze1[curx][cury-1]!='#')&&(maze1[curx][cury-1]!='4'))
        {
            System.out.print("left      ");
             if((maze1[curx][cury-1]=='G'))
            {
                System.out.println("inG");
                if(atscrossed==ortry1.anos)
                {
                    goalfound=true;
                    System.out.println("===="+(stepcount+1));
                }else
                {
                    statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed, stepcount+1));
                }
            }else   if(maze1[curx][cury-1]=='@')
            {
                System.out.println("in@");
                statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed+1, stepcount+1));
            }else if(maze1[curx][cury-1]=='.')
            {
                System.out.println("in.");
                statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed, stepcount+1));
            }
            else if(maze1[curx][cury-1]=='1')
            {
                System.out.println("in1");
                statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed, stepcount+1));
            }else if(maze1[curx][cury-1]=='2')
            {
                System.out.println("in2");
                statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed, stepcount+1));
            }else if(maze1[curx][cury-1]=='3')
            {
                System.out.println("in3");
                statequeue.add(new Mazestate(maze1,curx, cury-1, atscrossed, stepcount+1));
            }



        maze1=temp.maze2.clone();
        }
        //------------RIGHT[curx][cury+1]---------------
        if(((cury+1)<ortry1.w)&&(maze1[curx][cury+1]!='#')&&(maze1[curx][cury+1]!='4'))
        {
            System.out.print("right     ");
             if((maze1[curx][cury+1]=='G'))
            {
                System.out.println("inG");
                if(atscrossed==ortry1.anos)
                {
                    goalfound=true;
                    System.out.println("===="+(stepcount+1));
                }else
                {
                    statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed, stepcount+1));
                }
            }else   if(maze1[curx][cury+1]=='@')
            {
                System.out.println("in@");
                statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed+1,     stepcount+1));                       
            }else if(maze1[curx][cury+1]=='.')
            {
                System.out.println("in.");
                statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed, stepcount+1));
            }

            else if(maze1[curx][cury+1]=='1')
            {
                System.out.println("in1");
                statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed, stepcount+1));
            }else if(maze1[curx][cury+1]=='2')
            {
                System.out.println("in2");
                statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed, stepcount+1));
            }else if(maze1[curx][cury+1]=='3')
            {
                System.out.println("in3");
                statequeue.add(new Mazestate(maze1,curx, cury+1, atscrossed, stepcount+1));
            }

            maze1=temp.maze2.clone();

        }   
        for(int y=0;y<h;y++){System.out.println();
        for(int z=0;z<w;z++)
        {System.out.print(maze1[y][z]+"   ");}}

    }

}

}

class Mazestate
{
    char[][] maze2=null;
    int curx,cury;//current position
    int atscrossed;//no. of @ crossed
    int stepcount;//no. of steps taken;
    public Mazestate(char[][] maze1,int curx,int cury,int atscrossed,int stepcount) 
    {
        this.maze2=maze1.clone();
        this.curx=curx;
        this.cury=cury;
        this.atscrossed=atscrossed;
        this.stepcount=stepcount;
    }
}

Answer 1

您的问题出在char[][] maze1=temp.maze2;，位于方法populatequeue()的开头。

maze1 和 temp.maze2 现在都指向同一对象(您正在复制引用，而不是对象)，因此当您修改 maze1 或 temp.maze2 时，您正在更改同一对象。

如果你想创建两个不同的对象，你可以使用方法clone()。

char[][] maze1 = temp.maze2.clone();