java - 迷宫，使用堆栈寻找最佳路径

Question

我有一个生成随机迷宫的程序。迷宫中会显示一个红点，并且迷宫中的每个方 block 都会闪烁红点。迷宫中的所有 block 都是 == 1，如果红点穿过该 block ，它就会递增++。红点朝最小数字的方向移动，这样它就不会陷入死胡同的无限循环中。一旦到达终点，我就解决了迷宫。这就是我遇到困难的地方，我试图打印红点以找到最佳路线，一直回到起点。我使用了一个堆栈类来记录红点移动位置的所有 y 和 x 分量。我能够追溯红点所在的每个位置，但这不是最佳解决方案。

我的问题是如何仅在最佳路径中打印红点追踪。我解决这个问题的想法是检查并查看之前访问过的堆栈的坐标，如果是的话......找到它被访问的最后一个情况并打印直到该点的红点。这样它就永远不会遇到它走过的死胡同。solve() 方法包含红点穿过迷宫并返回的回溯和求解技术。

我不是最伟大的程序员，我仍在学习如何使用堆栈，我被难住了几个小时，不知道如何解决这个问题。请善意地解释一下你将如何使用我制作的堆栈来做到这一点。谢谢您

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

    /* Write a routine to solve the maze.
       Start at coordinates x=1, y=1, and stop at coordinates
       x=mw-1, y=mh-2.  This coordinate was especially dug out
       after the program called your digout function (in the "actionPerformed"
       method).
    */
  public void solve()
  {
      int x=1, y=1;
      Stack yourstack = null;
      drawdot(y,x);
      while(y!=mh-2 || x!=mw-2 &&  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); 
           yourstack = new Stack(y,x,yourstack); // creates new stack for each coordinate travelled
          }//while

      while(yourstack != null){
            yourstack = yourstack.tail;
            drawdot(yourstack.y,yourstack.x); // this will traceback every box ive been through
      }//while
  } // solve

class Stack{
    int x;
    int y;
    Stack tail;
    public Stack(int a, int b, Stack t){
        y = a;
        x=b;
        tail=t;
    }

}//stackclass



    ///////////////////////////////////////////////////////////////
    /// 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

当您追溯路径时，您当前只是返回堆栈 - 但这不是最短路径...

...只要你可以回去检查你周围的 M 值:

byte valueOfFieldNorthOfXY = M[x][y-1]; //x/y is your current position
byte valueOfFieldWesthOfXY = M[x-1][y]; 
byte  ...;
byte  ...; //and so on...

虽然您的求解方法 simplay 中的第一个 while 循环通过淹没迷宫来解决迷宫，但第二个 while 方法用于返回...

当我说洪水时，我的意思是:每当“步行者”经过一个田地时，M[x][y]的值就会增加1(当“步行者”在田地 5 上行走 3 倍时)/6 那么 M[5][6] 的值 = 3)

因此，当您从末尾 (@40/50) 返回到开头 (@1/1) 时，您将执行以下算法:

1)  i stand on x/y
2)  i check the values north/east/south/west of me
2a) if i come from north, then i ignore the north field
2 ) ... and so on...
2d) if i come from west , then i ignore the west field
3)  i pick that direction, where the value is the least
4)  put the current field int your packPathStack and walk to 
    the 'best' direction
5)  repeat (go back to Nr.1) until you are @1/1

example
? 4 ?   //i'm standing at X (x/y)
2 x f   //? are values from walls or not yet considerd
? ? ?   //f is where i come from

--> i pick direction WEST(2) because thats less than NORTH(4)

实现这个算法，你就会得到一个新的堆栈，我称之为yourPathBackStack

Stack yourPathBackStack = new Stack();
while(x != 1 && y != 1 ){ //x/y = 1/1 = start - do it until you are there (Nr. 5)

    // 1)  i stand on x/y
    int x = yourPathBackStack.x;
    int y = yourPathBackStack.y;

    // 2)  i check the values north/east/south/west of me
    byte valueOfFieldNorthOfXY = ... ; //as seen above

    // 2a) if i come from north, then i ignore the north field
    if (yourstack.tail.x == x && yourstack.tail.y == y-1){
        //check - i DO come from north
        //make then valueOfFieldNorthOfXY very high
        valueOfFieldNorthOfXY = 100; //it's the same as ignoring
    }

    // 2 ) ... and so on...

    // 2d) if i come from west , then i ignore the west field
    if (yourstack.tail.x == x-1 && ...// as seen above

    // 3)  i pick that direction, where the value is the least
    int direction = NORTH; //lets simply start with north;
    byte maxValue = 100;
    if ( valueOfFieldNorthOfXY < maxValue ){ //First north
        maxValue = valueOfFieldNorthOfXY;
        direction = NORTH;
    }
    if ( valueOfFieldWestOfXY < maxValue ){ //Then east
        maxValue = valueOfFieldWestOfXY ;
        direction = WEST;
    }    
    //then the also other directions
    if ( value ... //as seen above


    // 4)  put the current field int your yourPathBackStack and walk to 
    //     the 'best' direction

    int newx = x;
    int newy = y;
    if (direction == NORTH){ //direction has been caclulated above
        newy = newy - 1;
    }
    if (direc ... //with all other direction)

    yourPathBackStack = new Stack(newx, newy, yourPathBackStack );
    drawdot(yourPathBackStack.y,yourPathBackStack.x); 

}