在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。希望這可以幫助。