import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;
public class CreateMap {
public int rows;
public int cols;
private int[][] map;//设立私有域,用来存储0或1,其中0代表障碍,1代表通路;
public int[][] getMap(){
return map;//获得map数组所存储的值
}
public CreateMap(int a, int b) {
this.rows = a;
this.cols = b;
map = new int[rows+2][cols+2];
}//创建CreateMap的有参构造方法,用来开辟空间储存map数组里的数据
//运用回溯法生成地图
public void division(int x, int y, int height, int width) {
//初始化整个迷宫为全部通路(外墙除外)
for(int i=1;i<=rows;i++) {
for(int j=1;j<=cols;j++) {
map[i][j]=1;
}
recursiveDivision(x, y, height, width);
}
}
private void recursiveDivision(int x, int y, int height, int width) {
int xWall, yWall;
Random r = new Random();
if(height<=2||width<=2) {
return;
}
//首先随机产生第偶数行,设置为墙
xWall=x+r.nextInt(height/2)*2+1;
for(int j=1;j<width;j++) {
map[xWall][j] = 0;
}
//再随机产生第偶数列,设置为障碍
yWall =y+r.nextInt(width/2)*2+1;
for(int i=1;i<height;i++) {
map[i][yWall]=0;
}
//随机选择在三个方向的墙上开通路,通路应开在奇数行,列。以左侧障碍墙方向1,顺时针旋转
int direct = r.nextInt(4) + 1;
switch(direct) {
case 1:
setDoor(xWall, y, xWall, yWall-1);
setDoor(x, yWall, xWall-1, yWall);
setDoor(xWall, yWall+1, xWall, y+width-1);
break;
case 2:
setDoor(x, yWall, xWall-1, yWall);
setDoor(xWall, yWall+1, xWall, y+width-1);
setDoor(xWall+1, yWall, x+height-1,yWall);
break;
case 3:
setDoor(xWall, yWall+1, xWall, y+width-1);
setDoor(xWall+1, yWall, x+height-1, yWall);
setDoor(xWall, y, xWall, yWall-1);
break;
case 4:
setDoor(xWall+1, yWall, x+height-1, yWall);
setDoor(xWall, y, xWall, yWall-1);
setDoor(x, yWall, xWall-1, yWall);
break;
}
//利用递归对每个子迷宫进行创建
recursiveDivision(x, y, xWall-x, yWall-y);//左上
recursiveDivision(x, yWall+1, xWall-x, y+width-1-yWall);//右上
recursiveDivision(xWall+1, yWall+1, x+height-1-xWall, y+width-1-yWall);//右下
recursiveDivision(xWall+1, y, x+height-1-xWall, yWall-y);//左下
}
private void setDoor(int x1, int y1, int x2, int y2) {
int pos;
Random r = new Random();
if(x1==x2) {
pos = y1 + r.nextInt((y2 - y1)/2 + 1) * 2;
map[x1][pos] = 1;
}
else if(y1==y2) {
pos = x1 + r.nextInt((x2-x1)/2 + 1) * 2;
map[pos][y1] = 1;
}
else {
System.out.println("位置错误");
return;
}
}
}
给你个正确的。
import java.util.LinkedList;
public class DfsRatMaze {
int min = Integer.MAX_VALUE;
int endX = 3; //目标点横坐标
int endY = 3; //目标点纵坐标
int width = 5; //迷宫宽度
int height = 4; //迷宫高度
int[][] maze = new int[5][4];
int[][] mark = new int[5][4];
LinkedList<Integer> map = new LinkedList<>();
public void dfs(int startX, int startY, int step) {
int[][] next = new int[][] { //按右->下->左->上的顺序尝试
{1, 0},
{0, 1},
{-1, 0},
{0, -1}
};
int nextX, nextY;
int posible;
if(startX == endX && startY == endY) {
if(step < min)
min = step;
for(int i = map.size() - 1; i >= 0; i -= 2){
nextX = map.get(i);
nextY = map.get(i - 1);
System.out.print("[" + nextX + "," + nextY + "]");
if(i != 1)
System.out.print("->");
}
System.out.println();
return;
}
for(posible = 0; posible < next.length; posible++) { //按右->下->左->上的顺序尝试
nextX = startX + next[posible][0];
nextY = startY + next[posible][1];
if(nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) { //超出边界
continue;
}
if(maze[nextX][nextY] == 0 && mark[nextX][nextY] == 0) { //非障碍且未标记走过
map.push(nextX);
map.push(nextY);
mark[nextX][nextY] = 1;
dfs(nextX, nextY, step + 1); //递归调用, 移动到下一格
mark[nextX][nextY] = 0;
map.pop();
map.pop();
}
}
}
/*
* 初始化迷宫
*/
public void initMaze() {
this.maze = new int[width][height];
this.mark = new int[width][height];
this.maze[2][0] = 1;
this.maze[1][2] = 1;
this.maze[2][2] = 1;
this.maze[3][2] = 1;
this.mark[0][0] = 1;
//打印迷宫 _表示可通行 *表示障碍 !表示目标
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
if(x == endX && y == endY) {
System.out.print("! ");
} else if(this.maze[x][y] == 1) {
System.out.print("* ");
} else {
System.out.print("_ ");
}
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
int startX = 0;
int startY = 0;
DfsRatMaze d = new DfsRatMaze();
d.initMaze();
d.dfs(startX, startY, 0);
if(d.min < Integer.MAX_VALUE)
System.out.println("最少需要" + d.min + "步");
else
System.out.println("目标地点无法到达");
}
}