谁有迷宫地图的算法？

public class Mouse {
private int startI, startJ;  // 入口
private int endI, endJ;  // 出口
private boolean success = false;public static void main(String[] args) {
int[][] maze = {{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};System.out.println("显示迷宫：");
for(int i = 0; i < maze.length; i++) {
   for(int j = 0; j < maze[0].length; j++)
      if(maze[i][j] == 2)
          System.out.print("█");
      else
          System.out.print("  ");
System.out.println();
}Mouse mouse = new Mouse();
mouse.setStart(1, 1);
mouse.setEnd(5, 5);if(!mouse.go(maze)) {
   System.out.println("\n没有找到出口！");
}
else {
   System.out.println("\n找到出口！");
   for(int i = 0; i < maze.length; i++) {
      for(int j = 0; j < maze[0].length; j++) {
         if(maze[i][j] == 2)
            System.out.print("█");
         else if(maze[i][j] == 1)
             System.out.print("◇");
         else
             System.out.print("  ");
       }
    System.out.println();
}
}
}public void setStart(int i, int j) {
this.startI = i;
this.startJ = j;
}        public void setEnd(int i, int j) {
this.endI = i;
this.endJ = j;
}        public boolean go(int[][] maze) {
return visit(maze, startI, startJ);
}private boolean visit(int[][] maze, int i, int j) {
maze[i][j] = 1;
if(i == endI && j == endJ)
   success = true;
if(!success && maze[i][j+1] == 0)
   visit(maze, i, j+1);
if(!success && maze[i+1][j] == 0)
   visit(maze, i+1, j);
if(!success && maze[i][j-1] == 0)
   visit(maze, i, j-1);
if(!success && maze[i-1][j] == 0)
   visit(maze, i-1, j);
if(!success)
   maze[i][j] = 0;
return success;     }}
自己写出来了
可能还有些问题，但是测试了几个还是可以用的
package com.marssoft.test;import java.util.ArrayList;/**
* 迷宫算法。
* @author Mars.CN
*
*/
public class MarsMaze {
private int width , height;
private Position start = null;//起点位置。
private Position end = null;//终点位置。
private int[][] maze;//迷宫

public int getWidth() {
return width;
} public int getHeight() {
return height;
} public static void main(String[] args){
//double s = System.currentTimeMillis();
MarsMaze maze = new MarsMaze(100,10);
//double e = System.currentTimeMillis();
//System.out.println(e-s);

for(int i=0 ; i<maze.getWidth()+2 ; i++){
System.out.print("■");
}
System.out.println();

for(int i=0 ; i<maze.getHeight() ; i++){
if(i==0){
System.out.print("  ");
}else{
System.out.print("■");
}

for(int f=0 ; f<maze.getWidth() ; f++){
//System.out.print(maze.getMaze()[f][i] + " ");
if(maze.getMaze()[f][i]==1){
System.out.print("■");
}else{
System.out.print("  ");
}
}
if(i==maze.getHeight()-1){
System.out.print("  ");
}else{
System.out.print("■");
}
System.out.println();
}

for(int i=0 ; i<maze.getWidth()+2 ; i++){
System.out.print("■");
}
System.out.println();
maze.getMaze();

}

/**
* 初始化，设置迷宫的大小。
* @param width
* @param height
*/
public MarsMaze(int width , int height){
this.width = width;
this.height = height;
init();
}

/**
* 获得迷宫图。
* @return
*/
public int[][] getMaze(){

return maze;
}

/**
* 初始化迷宫。
*/
public void init(){
int[][] maze = new int[width][height];
ArrayList<Position> beixuan = new ArrayList<Position>();//准备经过的
ArrayList<Position> dailiu = new ArrayList<Position>();//已经走过的
ArrayList<Position>zhongdian = new ArrayList<Position>();//所有终点
start = new Position(null,0,0);//起点
end = new Position(null,width-1,height-1);;//终点，暂定终点为最后一个
Position now = start;//当前点
maze[now.getX()][now.getY()]=2;//表示已经被访问过
do{
//判断顺序左右上下
if(now.getX()-1>=0){
//左边选择
if(maze[now.getX()-1][now.getY()]==0){
beixuan.add(new Position(now,now.getX()-1,now.getY()));
maze[now.getX()-1][now.getY()]=1;
}
}
if(now.getX()+1<width){
//右边选择
if(maze[now.getX()+1][now.getY()]==0){
beixuan.add(new Position(now,now.getX()+1,now.getY()));
maze[now.getX()+1][now.getY()]=1;
}
}
if(now.getY()-1>=0){
//上边选择
if(maze[now.getX()][now.getY()-1]==0){
beixuan.add(new Position(now,now.getX(),now.getY()-1));
maze[now.getX()][now.getY()-1]=1;
}
}
if(now.getY()+1<height){
//下边选择
if(maze[now.getX()][now.getY()+1]==0){
beixuan.add(new Position(now,now.getX(),now.getY()+1));
maze[now.getX()][now.getY()+1]=1;
}
}

if(beixuan.size()==0){
//表示终点
if(!now.equals(end)){
zhongdian.add(now);
}
}else{
while(beixuan.size()>0){
int z = new Double(Math.random()*beixuan.size()).intValue();
Position pos = beixuan.get(z);
dailiu.add(pos);
beixuan.remove(z);
}
}

if(dailiu.size()>0){
Position pos = dailiu.get(dailiu.size()-1);
dailiu.remove(dailiu.size()-1);
maze[pos.getX()][pos.getY()]=2;
now = pos;
}
if(now.equals(end)){
end = now;
}
}while(dailiu.size()>0);

//深度查询做出迷宫路径
int[][] m = new int[width][height];
// Position f = end;
// while(f!=null){
// m[f.getX()+1][f.getY()+1]=1;
// f=f.getFather();
// }

//设置迷宫终点
for(int i=0 ; i<zhongdian.size() ; i++){
m[zhongdian.get(i).getX()][zhongdian.get(i).getY()]=1;
}
this.maze = m;
}

/**
* 连表中的位置和上级
* @author Mars.CN
*
*/
private class Position{
private Position father = null;
private int x , y;

public Position(Position father , int x , int y){
this.father = father;
this.x=x;
this.y=y;
} public Position getFather() {
return father;
} public int getX() {
return x;
} public int getY() {
return y;
}

public boolean equals(Position pos){
if(this.x==pos.x && this.y==pos.y){
return true;
}else{
return false;
}
}
}
public Position getStart() {
return start;
} public Position getEnd() {
return end;
}
}
import java.io.*;
import java.util.*;
/** 老鼠走迷宫程序
*
* @author bigbug
* @version 1.0
*//** Direction 方向枚举类型，八个方向。从北方NORTH到西北WESTNORTH按顺时针方向排列*/
enum Direction{
    NORTH,
    EASTNORTH,
    EAST,
    EASTSOUTH,
    SOUTH,
    WESTSOUTH,
    WEST,
    WESTNORTH
}
/** Maze 迷宫类:
*  rows:迷宫的行数。
*  columns:迷宫的列数。
*  ma：二维字符型数组，其中'1'表示墙，'0'表示通路。在老鼠走迷宫过程中会留下痕迹，'2'表示只路过一次，'3'表示路过二次。
*  entranceRow,entranceColumn：分别表示迷宫入口的行、列。
*  exitRow,exitColumn:分别表示迷宫出口的行、列。
*/
class Maze{
    int rows,columns;
    char[][] ma;
    int entranceRow=0,entranceColumn=0;
    int exitRow=14,exitColumn=14;

  /** Maze类的构造方法。
  * 其实入口和出口的行、列也应该在构造方法中初始化。
  * 但为了省事，在上面的声明中初始化了。
  * @param r 表示迷宫的行数。
  * @param c 表示迷宫的列数。
  */
  Maze(int r,int c){
      rows=r;
      columns=c;
      ma=new char[rows][columns];
      try{
          //由于2.txt文件的格式，只好用BufferedReader，因为要一行行读出来。
          //FileInputStream()方法会抛出FileNotFoundException异常
          BufferedReader br=new BufferedReader(new InputStreamReader(new FileInputStream("f:/java/2.txt")));
          String s="";
          for(int i=0;i<rows;i++){
              //readLine()方法会抛出一个IOException异常
              s=br.readLine();
              for(int j=0;j<columns;j++){
                  ma[i][j]=s.charAt(j);
            }
      }
    }catch(FileNotFoundException e){
          System.out.println("File f:\\java\\2.txt not fount!!");
      }catch(IOException ie){
              ie.printStackTrace();
      }

  }//Maze()
  /**打印出迷宫示意图，▇表示墙，□表示通路，m表示只通过一次，p表示通过了两次及以上。*/
  void printMaze(){
      for(int i=0;i<rows;i++){
          for(int j=0;j<columns;j++){
              if(ma[i][j]=='1'){
                  System.out.print("▇");
              }else if(ma[i][j]=='0'){
                  System.out.print("□");
              }else if(ma[i][j]=='2'){
                  System.out.print("m ");
              }else{
                  System.out.print("p ");
              }
          }
          System.out.println("");

      }
  }
}
/** Mouse类
* posRow,posColumn表示老鼠在迷宫的当前位置，即所处的行，列
* direction 老鼠要向那个方向走
* maze 迷宫。
* trace 一个堆栈，存放老鼠走过的地方（迷宫中的行、列），以便走不通时，能退回到上一步路过的位置。
* passable 一个boolean型数组，用以标记迷宫中的某方格mouse是否能走.没有这个数组，程序可能会有死循环。
* 如pasable[i][j]的值为false 表示迷宫中行为i,列为j的方格老鼠不可以走。要么这个格是墙，要么曾经走过。
*/
public class Mouse{
        int posRow,posColumn;
        Direction direction;
        Maze maze;
        Stack trace;
        boolean[][] passable;
        /**Mouse 类的构造方法*/
        Mouse(int posRow,int posColumn,Direction d){
            this.posRow=posRow;
            this.posColumn=posColumn;
            direction=d;
            maze=new Maze(15,15);
            trace=new Stack();
            passable=new boolean[maze.rows][maze.columns];
            //下面的循环是对passable数组进行初始化，对照迷宫的ma进行，对墙打false标记，通路打true标记
            for(int i=0;i<maze.rows;i++){
                for(int j=0;j<maze.columns;j++){
                    if(maze.ma[i][j]=='1'){
                        passable[i][j]=false;
                    }else{
                        passable[i][j]=true;
                    }
                }
            }
        }
        /**探测下一个可以走的位置，并走过去，如果成功返回true，否则返回false*/
        boolean getNextPosition(){
        //增强型for循环，continue,break也可以用在其中。
        //关于枚举类型的应用可以查http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html。
        //这个循环遍历了所有的方向，显然可以优化。可以从当前的方向顺时针转到WESTNORTH。要用到EnumSet类。
        for(Direction d:Direction.values()){
            //判断下一位置是否超出了迷宫的边界
            //对于方向d，老鼠从当前位置朝着d方向走时，行，列的值会变化，变化的值由getRowOffset方法和getColumnOffset方法得到。
            if(posRow+getRowOffset(d)<0||posRow+getRowOffset(d)>=maze.rows||posColumn+getColumnOffset(d)<0||posColumn+getColumnOffset(d)>=maze.columns)
               continue;
            //如果下一位置可以走，就走过去，否则进行下一次循环继续找。
            if(!passable[posRow+getRowOffset(d)][posColumn+getColumnOffset(d)]){
                continue;
            }else{
                posRow+=getRowOffset(d);
                posColumn+=getColumnOffset(d);
                direction=d;
                return true;
            }
        }
        //程序能运行到这里，表示上面的return true；没有被执行过，也就是没有找到一个可以走的位置，返回false;
        return false;
    }
    /** 走迷宫
    */
    boolean throughMaze(){
        trace.push(posRow);         //把入口的行值压入栈
        trace.push(posColumn);      //把入口的列值压入栈
        //把入口时老鼠的方向压入栈，在本程序中这个动作没有必要，但如果要优化getNextPosition()中的for循环，这个动作就是必需的了。
        trace.push(direction);
        passable[posRow][posColumn]=false;  //当值位置标记为不可走。
        //当栈不空，且没有到达出口时一直循环。
        //栈空表示老鼠退回到了入口。这时表示这个迷宫没有通路到达出口。
        while(!trace.empty()&&(posRow!=maze.exitRow||posColumn!=maze.exitColumn)){
            if(getNextPosition()){
                trace.push(posRow);
                trace.push(posColumn);
                trace.push(direction);
                passable[posRow][posColumn]=false;
                maze.ma[posRow][posColumn]='3';   //留下足迹，'3'表示路过多次，这是假设，走完迷宫后再做修正。
            }else{  //从当前位置没有找到可以通过的方格时，下面的动作就是退回上一步，以便从那里再找。
                //退回上一步，就是出栈，留意出栈的顺序。
                direction=(Direction)trace.pop();
                posColumn=((Integer)trace.pop()).intValue();
                posRow=((Integer)trace.pop()).intValue();
            }
        }
        //退出while循环之后，栈空表示迷宫没有通路。
        if(trace.empty()){
            return false;
        }else{       //栈非空，有通路，栈中存放的就是老鼠只经过一次的那些位置。
            //一直出栈，直到栈为空。
            while(!trace.empty()){
                int r,c;
                trace.pop(); //方向出栈，下面用不到方向了，数据扔掉，但动作不可少。
                c=((Integer)trace.pop()).intValue();
                r=((Integer)trace.pop()).intValue();
                maze.ma[r][c]='2';  //把行为r,列为c的方格修正为只经过一次。
            }
            return true;
        }
    }
    /**返回老鼠当前方格的行值与d方向的方格的行值偏移量
    * @param d 方向*/
    int getRowOffset(Direction d){
        int offset=2;
        switch(d){
            case NORTH:     offset= -1; break;//从当前方格走到北面的方格，行值应该减1.下面类似。
            case EASTNORTH: offset= -1; break;
            case EAST:      offset= 0; break;
            case EASTSOUTH: offset= 1; break;
            case SOUTH:     offset= 1; break;
            case WESTSOUTH: offset= 1; break;
            case WEST:      offset= 0; break;
            case WESTNORTH: offset= -1;
        }
        return offset;
    }
    /**返回老鼠当前方格的列值与d方向的方格的列值的偏移量*/
    int getColumnOffset(Direction d){
        int offset=2;
        switch(d){
            case NORTH:     offset= 0; break; //从前方格走到北面的方格，列值不变。下面类似。
            case EASTNORTH: offset= 1; break;
            case EAST:      offset= 1; break;
            case EASTSOUTH: offset= 1; break;
            case SOUTH:     offset= 0; break;
            case WESTSOUTH: offset= -1; break;
            case WEST:      offset= -1; break;
            case WESTNORTH: offset= -1;
        }
        return offset;
    }
    public static void main(String[] args){
        Mouse mouse=new Mouse(0,0,Direction.NORTH);
        System.out.println("The maze:");
        mouse.maze.printMaze();  //打印初始状态的迷宫
        /*试图清除dos窗口的屏幕，不成功。可能执行，cmd是打开一个新的dos窗口，所以cls是清除新窗口的屏幕，而不是当前的。
        try{
            Runtime.getRuntime().exec("cmd.exe /k cls");
        }catch(Exception e){
            e.printStackTrace();
        }
        */
        if(mouse.throughMaze()){
            System.out.println("Trace of mouse:");
            mouse.maze.printMaze();  //打印经过老鼠践踏后的迷宫:)
            System.out.println("m---pass by  for once .  p----pass by many times ");
        }else{
            System.out.println("No pass!");
        }
    }
}

调试易

谁有迷宫地图的算法？

解决方案 »