在java中寻找迷宫的解决方案

Question

我有一个项目在随机生成的迷宫的第一个盒子里面有一个红点，这个点应该跟随它通过盒子的方式并找到迷宫的末端。现在，如果它陷入死胡同，它应该回到它的路径开始的地方，而不是沿着那条路走下去，那会导致死路一条。我做到了，所以每个盒子都代表＃1，这样当红点在盒子上移动时，它会增加1，因此它可以实现它的位置。它总是应该尽可能地降到最低的数量，所以它永远不会回到已经到了的死角。我能够达到迷宫的尽头，但我遇到了两个问题。

我写的所有这些工作的方法是solve（）函数。我不明白为什么发生两件事... 第一件事是，当红点来到一个死胡同的分支，有时它只是去一个死胡同，到一个不同的死胡同，回到同样的死胡同。当我试图让它只朝向有1或更低数字的盒子时，它们走到相同的'数字'。 第二件事是，一旦它不可避免地到达迷宫的尽头..红点进入绿色区域，在那里我特别说在while循环中，它不能在绿色框中。

如果M [y] [x] = 0，那么它是一个绿色框，如果它= 1，那么它是一个黑色框。任何高于1的东西也将在盒子内。

你的帮助是高度赞赏的，因为一直困住这个问题几个小时，似乎无法找到问题。

问题仍然存在，在解决（）方法

import java.awt.*; 
import java.awt.event.*; 
import java.awt.Graphics; 
import javax.swing.*; 

public class mazedfs extends JFrame implements KeyListener 
{ 
/* default values: */ 
private static int bh = 16;  // height of a graphical block 
private static int bw = 16; // width of a graphical block 
private int mh = 41; // height and width of maze 
private int mw = 51; 
private int ah, aw; // height and width of graphical maze 
private int yoff = 40; // init y-cord of maze 
private Graphics g; 
private int dtime = 40; // 40 ms delay time 
byte[][] M; // the array for the maze 
public static final int SOUTH = 0; 
public static final int EAST = 1; 
public static final int NORTH = 2; 
public static final int WEST = 3; 

public static boolean showvalue = true; // affects drawblock 

// args determine block size, maze height, and maze width 
public mazedfs(int bh0, int mh0, int mw0) 
{ 
    bh = bw = bh0; mh = mh0; mw = mw0; 
    ah = bh*mh; 
    aw = bw*mw; 
    M = new byte[mh][mw]; // initialize maze (all 0's - walls). 
    this.setBounds(0,0,aw+10,10+ah+yoff);  
    this.setVisible(true); 
    this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
    try{Thread.sleep(500);} catch(Exception e) {} // Synch with system 
    this.addKeyListener(this); 
    g = getGraphics(); //g.setColor(Color.red); 
    setup(); 
} 

public void paint(Graphics g) {} // override automatic repaint 

public void setup() 
    { 
    g.setColor(Color.green); 
    g.fill3DRect(0,yoff,aw,ah,true); // fill raised rectangle 
    g.setColor(Color.black); 
    //  showStatus("Generating maze..."); 
    digout(mh-2,mw-2); // start digging! 
    // digout exit 
    M[mh-1][mw-2] = M[mh-2][mw-1] = 1; 
    drawblock(mh-2,mw-1); 
    solve(); // this is the function you will write for parts 1 and 2 
    play(); // for part 3 
    } 

    public static void main(String[] args) 
    { 
     int blocksize = bh, mheight = 41, mwidth = 41; // need to be odd 
     if (args.length==3) 
     { 
      mheight=Integer.parseInt(args[0]); 
      mwidth=Integer.parseInt(args[1]); 
      blocksize=Integer.parseInt(args[2]); 
     } 
     mazedfs W = new mazedfs(blocksize,mheight,mwidth); 
    } 

public void drawblock(int y, int x) 
    { 
    g.setColor(Color.black); 
    g.fillRect(x*bw,yoff+(y*bh),bw,bh); 
    g.setColor(Color.yellow); 
    // following line displays value of M[y][x] in the graphical maze: 
    if (showvalue) 
     g.drawString(""+M[y][x],(x*bw)+(bw/2-4),yoff+(y*bh)+(bh/2+6)); 
    } 

    void drawdot(int y, int x) 
    { 
    g.setColor(Color.red); 
    g.fillOval(x*bw,yoff+(y*bh),bw,bh);    
     try{Thread.sleep(dtime);} catch(Exception e) {} 
    } 

    ///////////////////////////////////////////////////////////////////// 

/* function to generate random maze */ 
public void digout(int y, int x) 
{ 
    M[y][x] = 1; // digout maze at coordinate y,x 
    drawblock(y,x); // change graphical display to reflect space dug out 


    int dir = (int)(Math.random()*4); 

    for (int i=0;i<4;i++){ 
    int [] DX = {0,0,2,-2}; 
    int [] DY = {-2,2,0,0}; 
    int newx = x + DX[dir]; 
    int newy = y + DY[dir]; 
    if(newx>=0 && newx<mw && newy>=0 && newy<mh && M[newy][newx]==0) 
     { 
     M[y+DY[dir]/2][x+DX[dir]/2] = 1; 
     drawblock(y+DY[dir]/2,x+DX[dir]/2); 
     digout(newy,newx); 
     } 
    dir = (dir + 1)%4;} 
} // digout 


    public void solve() // This is the method i need help with. 
    { 
    int x=1, y=1; 
    drawdot(y,x); 
    while(y!=mh-1 || x!=mw-1 && M[y][x]!=0){ 
      int min = 0x7fffffff; 
      int DX = 0; 
      int DY = 0; 
     if (y-1>0 && min>M[y-1][x] && M[y-1][x]!=0){ 
      min = M[y-1][x]; 
      DX = 0; 
      DY = -1; 
     }//ifNORTH 
     if (y+1>0 && min>M[y+1][x] && M[y+1][x]!=0){ 
      min = M[y+1][x]; 
      DY = 1; 
      DX = 0; 
     }//ifSOUTH 
     if (x-1>0 && min>M[y][x-1] && M[y][x-1]!=0){ 
      min = M[y][x-1]; 
      DX = -1; 
      DY = 0; 
     }//ifWEST 
     if (x+1>0 && min>M[y][x+1] && M[y][x+1]!=0){ 
      min = M[y][x+1]; 
      DX = 1; 
      DY = 0; 
     }//ifEAST 

     M[y][x]++; 
     drawblock(y,x); 
     x = x+DX; 
     y = y+DY; 
     drawdot(y,x); 
    }//while 


     // modify this function to move the dot to the end of the maze. That 
     // is, when the dot reaches y==mh-2, x==mw-2 
    } // solve 


    /////////////////////////////////////////////////////////////// 
    /// For part three (save a copy of part 2 version first!), you 
    // need to implement the KeyListener interface. 

    public void play() // for part 3 
    { 
    // code to setup game 
    } 
    // for part 3 you may also define some other instance vars outside of 
    // the play function. 

    // for KeyListener interface 
    public void keyReleased(KeyEvent e) {} 
    public void keyTyped(KeyEvent e) {} 
    public void keyPressed(KeyEvent e) // change this one 
    { 
    int key = e.getKeyCode();  // code for key pressed  
    System.out.println("YOU JUST PRESSED KEY "+key); 
    } 

} // mazedfs 


//////////// 
// define additional classes (stack) you may need here. 

Answer 1

造成你所面临的第二个问题（点移动到绿盒）的问题在于while循环条件y!=mh-1 || x!=mw-1 && M[y][x]!=0。条件评估为y!=mh-1 ||(x!=mw-1 && M[y][x]!=0)，因为&&优先于||和||只需要其操作数中的一个为真。在你的情况下，y!=mh-1仍然在迷宫的尽头。因此循环继续，点移动到绿色区域。要解决该问题，请将条件修改为(y!=mh-1 || x!=mw-1) && M[y][x]!=0。希望这可以帮助。