我试图找到从起点“ 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;
}
}
最佳答案
您的问题出在方法char[][] maze1=temp.maze2;的开头populatequeue()。
现在，maze1和temp.maze2都指向同一个对象（您正在复制引用，而不是对象），因此，在修改maze1或temp.maze2时，您正在更改同一对象。
如果要创建两个不同的对象，可以使用clone（）方法。
char [] [] maze1 = temp.maze2.clone（）;