java 利用dfs生成简单的随机迷宫（效率不高）

利用深搜可以生成简单的迷宫，思路就是从起点执行dfs。当然你要首先用一个容器将四个方向的随机数装起来保证一定可以走。一个点一旦被走过就不会再走那个店，利用递归思想，因为这个点如果不成功在之前回溯的时候就已经便利了所有可能，如果表标记取消掉，那么就会增加巨大计算量。
可以这样打个比方，从北京到南京，到苏州，到上海。现在到了苏州发现无论怎么走了十万八千里都到不了上海，那么苏州这个点就会被定位标记，往回走发现南京也不行。换路。在从北京到合肥到苏州到上海。遇到苏州就直接pass掉，因为它得不到结果。（不太形象但是就是这个意思）。
如果直接从左上到右下，地图可能会不均与有点难看，那么还可以加一个从右上到坐下的只走左和下的路径。（不能随机四个方向，否则太乱联通太多）。附上代码

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class 迷宫 {
	static int x[]= {1,0,-1,0};//下。右 ,上，
	static int y[]= {0,1,0,-1};	
	static int time=0;//路径总长度
	static int time2=0;//计算总次数
	static int length;
	static boolean c=false;
	public static void main(String[] args)
	{
		System.out.println("请输入图的边长");
		Scanner sc=new Scanner(System.in); length=sc.nextInt();
		draw(length); } private static void draw(int m) { boolean b[][]=new boolean[m][m];	 //标记  char a[][]=new char[m][m]; for(int i=0;ilength-1||i x[s]<0||j y[s]>length-1||j y[s]<0)//不满足题意的。 { continue; } else if(!b[i x[s]][j y[s]])//前面没有走过 { char biaoji=a[i][j]; time ;time2 ; a[i][j]='6'; dfs(a,b,i x[s],j y[s],l,m); if(!c)//终止递归，防止破坏数组。 {a[i][j]=biaoji; //b[i][j]=false;//不需要标记回溯，因为这条路走过就走过，换路走 time--;} else//返回 {return;} } } } }
	 static void dfs2(char[][] a, boolean[][] b, int i, int j, int l, int m) { if(i==l&&j==m) {a[i][j]='6'; System.out.println(time " " time2); c=true;}//证明已经找到 else if(!c)//没找到结束 { b[i][j]=true; List list=new ArrayList(); List list2=new ArrayList();//存取排序后的数字 for(int i1=0;i1<2;i1 ){list.add(i1);} for(int i2=0;i2<2;i2 ) {
	 int team=(int) (Math.random()*list.size());
	 list2.add(list.get(team));
	 list.remove(team); } for(int k=0;k<2;k ) { int s=(int) list2.get(k) 1; //System.out.println(s); if(i x[s]>length-1||i x[s]<0||j y[s]>length-1||j y[s]<0)//不满足题意的。 { continue; } else if(!b[i x[s]][j y[s]])//前面没有走过 { char biaoji=a[i][j]; time ;time2 ; a[i][j]='6'; dfs2(a,b,i x[s],j y[s],l,m); if(!c) {a[i][j]=biaoji; //b[i][j]=false;//不需要标记回溯，因为这条路走过就走过，换路走 time--;} else//返回 {return;} } } } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
 

注意测试数据不能太大，否则会爆内存。
当然这种迷宫是很low的，如果生成另一种迷宫还需要并查集知识。

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/80380881