自己写出来了 可能还有些问题,但是测试了几个还是可以用的 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);
/** * 获得迷宫图。 * @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(); // }
/** * 连表中的位置和上级 * @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; } }
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!");
}
}
}