fork download
copy 
  1.  
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. import static java.util.Arrays.*;
  6. import static java.util.Collections.*;
  7. import static java.lang.Math.*;
  8.  
  9. class RandomMaze {
  10.  
  11. 	int MAX = 30;
  12. 	boolean[][][] map;
  13. 	int[][] arrow;
  14. 	LinkedList<int[]> route;
  15. 	HashSet<P> used, route_h;
  16. 	int sx = 1, sy = 1, ex = MAX, ey = MAX;
  17. 	int LEN = MAX / 2;
  18. 	MyDirect direct;
  19.  
  20. 	Random rnd;
  21.  
  22. 	int[] dx = {-1,0,1,0};
  23. 	int[] dy = {0,-1,0,1};
  24.  
  25. 	public RandomMaze() {
  26. 		// TODO 自動生成されたコンストラクター・スタブ
  27. 		map = new boolean[MAX+2][MAX+2][4];
  28. 		arrow = new int[MAX+2][MAX+2];
  29. 		for (int[] a : arrow) fill(a, -1);
  30. 		for (int i=0;i<MAX+2;i++) {
  31. 			map[i][1][0]   = map[i][0][2]     = map[1][i][1]   = map[0][i][3]     = true;
  32. 			map[i][MAX][2] = map[i][MAX+1][0] = map[MAX][i][3] = map[MAX+1][i][1] = true;
  33. 			arrow[i][0] = arrow[i][MAX+1] = 1; arrow[0][i] = arrow[MAX+1][i] = 0;
  34. 		}
  35.  
  36. 		route = new LinkedList<int[]>();
  37. 		route_h = new HashSet<P>();
  38. 		used = new HashSet<P>();
  39. 		direct = new MyDirect();
  40. 		rnd = new Random(System.currentTimeMillis());
  41.  
  42. //		print_board();
  43. 		create_route();
  44. //		print_board();
  45. 		while (! is_finish()) {
  46. 			P[] puts = next_puts();
  47. 			int r = rnd.nextInt(puts.length);
  48. 			create_branch(puts[r].x, puts[r].y, puts[r].d);
  49. 		}
  50.  
  51. 		print_board();
  52. 	}
  53.  
  54. 	P[] next_puts() {
  55. 		ArrayList<P> puts = new ArrayList<P>();
  56. 		for (int y=1;y<=MAX;y++) for (int x=1;x<=MAX;x++) {
  57. 			if (arrow[y][x] >= 0) continue;
  58. 			for (int i=0;i<4;i++){
  59. 				if (map[y][x][i]) continue;
  60. 				if (arrow[y+dy[i]][x+dx[i]] < 0) continue;
  61. 				puts.add(new P(x, y, (i+2)%4));
  62. 				break;
  63. 			}
  64. 		}
  65. 		return puts.toArray(new P[]{});
  66. 	}
  67.  
  68. 	public void create_route() {
  69. 		int x = sx, y = sy, d = -1;
  70. 		while (x != ex || y != ey) {
  71. 			int nd = next(x, y, d, direct);
  72. //			debug(x, y, d);
  73. 			if (nd < 0) {
  74. 				used.add(new P(x, y));
  75. 				arrow[y][x] = 0;
  76. 				int[] undo = route.removeLast();
  77. 				int px = undo[0], py = undo[1], pd = undo[2];
  78. 				x = px; y = py; d = pd;
  79.  
  80. 				if (route_h.remove(new P(x, y))) {
  81. //					debug("ok");
  82. //					new Scanner(System.in).next();
  83. //					print_board();
  84. 				}
  85. 				continue;
  86. 			}
  87.  
  88. 			route.add(new int[]{x, y, d});
  89. 			d = nd;
  90. 			arrow[y][x] = d;
  91. 			route_h.add(new P(x, y));
  92. 			used.add(new P(x, y));
  93.  
  94. 			x += dx[d]; y += dy[d];
  95. 			create_wall(x, y, d);
  96. 		}
  97. 		route.add(new int[]{ex, ey, 2});
  98. 		route_h.add(new P(ex, ey));
  99. 		used.add(new P(ex, ey));
  100. 	}
  101.  
  102. 	private boolean on_route(int x, int y) {
  103. 		return route_h.contains(new P(x, y));
  104. 	}
  105.  
  106. 	private boolean used(int x, int y) {
  107. 		return used.contains(new P(x, y));
  108. 	}
  109.  
  110. 	public void create_branch(int cx, int cy, int cd) {
  111. 		int x = cx, y = cy, d = cd;
  112. 		Branch branch = new Branch();
  113. 		for(int cnt = 0;cnt < LEN;cnt++) {
  114. 			used.add(new P(x, y));
  115. 			arrow[y][x] = d;
  116. 			create_wall(x, y, d);
  117. 			int nd = next(x, y, d, branch);
  118. 			if (nd < 0) return;
  119. 			int nx = x + dx[nd], ny = y + dy[nd];
  120. 			x = nx; y = ny; d = nd;
  121. 		}
  122. 	}
  123.  
  124. 	private int next(int x, int y, int d, Direct direct) {
  125. 		boolean[] f = new boolean[4];
  126.  
  127. 		for (int i=0;i<4;i++) {
  128. 			if (i == (d+2)%4) {
  129. 				f[i] = true;
  130. 				continue;
  131. 			}
  132. 			if (arrow[y+dy[i]][x+dx[i]] >= 0) {
  133. 				f[i] = true;
  134. 				int arr = arrow[y+dy[i]][x+dx[i]];
  135. 				f[arr] = true;
  136. 			}
  137. 		}
  138.  
  139. 		if (f[0] & f[1] & f[2] & f[3]) return -1;
  140.  
  141. 		int dir;
  142. 		do {
  143. 			dir = direct.direct(x, y);
  144. 		} while(f[dir]);
  145. //		print_board();
  146. 		return dir;
  147. 	}
  148.  
  149. 	private void create_wall(int x, int y, int d) {
  150. 		for (int i=0;i<4;i++) if(i != (d+2)%4) {
  151. 			map[y][x][i] = map[y+dy[i]][x+dx[i]][(i+2)%4] |= used(x+dx[i], y+dy[i]);
  152. 		}
  153. 	}
  154.  
  155. 	private boolean is_finish() {
  156. 		return used.size() == MAX * MAX;
  157. 	}
  158.  
  159. 	public void print_board() {
  160. 		for (int i=0;i<MAX*2+1;i++) {
  161. 			int y = i / 2 + 1;
  162. 			if (i % 2 == 0) {
  163. 				for (int x=1;x<=MAX;x++) {
  164. 					System.out.print(" ");
  165. 					if (map[y][x][1]) System.out.print("-");
  166. 					else System.out.print(" ");
  167. 				}
  168. 				System.out.println();
  169. 			} else {
  170. 				for (int x=1;x<=MAX+1;x++) {
  171. 					if (map[y][x][0]) System.out.print("|");
  172. 					else System.out.print(" ");
  173. 					if (x == MAX+1) break;
  174. 					if (sx == x && sy == y) System.out.print("#");
  175. 					else if (ex == x && ey == y) System.out.print("*");
  176. 					else if (on_route(x, y)) System.out.print("o");
  177. 					else if (used(x, y)) System.out.print(" ");
  178. 					else System.out.print(" ");
  179. 				}
  180. 				System.out.println();
  181. 			}
  182. 		}
  183.  
  184. 		System.out.println();
  185. 	}
  186.  
  187. 	class P {
  188. 		int x, y, d;
  189. 		P(int x, int y) {
  190. 			this.x = x;
  191. 			this.y = y;
  192. 			d = 0;
  193. 		}
  194. 		P(int x, int y, int d) {
  195. 			this.x = x;
  196. 			this.y = y;
  197. 			this.d = d;
  198. 		}
  199.  
  200. 		public int hashCode() {
  201. 			return x * MAX + y;
  202. 		}
  203.  
  204. 		public boolean equals(Object o) {
  205. 			if (o instanceof P) {
  206. 				P p = (P) o;
  207. 				return x == p.x && y == p.y;
  208. 			}
  209. 			return false;
  210. 		}
  211. 	}
  212.  
  213. 	interface Direct {
  214. 		int direct(int x, int y);
  215. 	}
  216.  
  217. 	class MyDirect implements Direct{
  218. 		double[][] waights = {
  219. 				{0.40, 0.50, 0.90, 1.0},
  220. 				{0.45, 0.50, 0.55, 1.0},
  221. 				{0.05, 0.50, 0.95, 1.0},
  222. 				{0.45, 0.50, 0.55, 1.0},
  223. 				{0.15, 0.30, 0.65, 1.0}
  224. 		};
  225. 		int[] waight_d;
  226. 		int div;
  227. 		Random rnd;
  228.  
  229. 		public MyDirect() {
  230. 			rnd = new Random(System.currentTimeMillis());
  231. 			waight_d = new int[waights.length + 1];
  232. 			div = (2 * MAX / waights.length);
  233. 			for (int i=1;i<=waights.length;i++) {
  234. 				waight_d[i] = div * i;
  235. 			}
  236. 		}
  237. 		public int direct(int x, int y) {
  238. 			// TODO 自動生成されたメソッド・スタブ
  239. 			double r = rnd.nextDouble();
  240. 			int area = (x + y) / div;
  241. 			for (int i=0;;i++) if (r < waights[area][i]){
  242. 				return i;
  243. 			}
  244. 		}
  245. 	}
  246. 	class Branch implements Direct{
  247. 		Random rnd;
  248. 		public Branch() {
  249. 			// TODO 自動生成されたコンストラクター・スタブ
  250. 			rnd = new Random(System.currentTimeMillis());
  251. 		}
  252. 		public int direct(int x, int y) {
  253. 			// TODO 自動生成されたメソッド・スタブ
  254. 			return rnd.nextInt(4);
  255. 		}
  256.  
  257. 	}
  258.  
  259. 	void debug(Object... os) {
  260. 		System.out.println(Arrays.deepToString(os));
  261. 	}
  262.  
  263. 	public static void main(String[] args) {
  264. 		new RandomMaze();
  265. 	}
  266. }
  267.  
  268.  
  269.  
Success #stdin #stdout 0.14s 380544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|# o|o o o|o o o o o o  |           | |   |         |     | |
 -     -     -   - -   -   - -   - -     -   - -   -   - -  
|o o|o  |o o  | |o o o  |   |   |     |       | |   |       |
   -   - - - - -   - -   -   - -   - - - -       -   -   -  
|o|o o|     |o o o| |   |       |   |   |   |     |       | |
     -     -   -       - - -     -     - - -   - - - - - -  
|o o  | | |o o|   | |       | |   |   |     | |             |
   - -       -   -   - -   -         -     -     - - - - - -
| |     | |o o|         | |   | | |     |   | |       |     |
     - -   -   - - -   -     -   - - - -       - -   -   - -
| |   |     |o|   |     |   | |     |     | |   | |   |     |
     -   - -         - - - -       -   - -   -       - - -  
| |   |      o| | |         |   |     |   |     |   |   |   |
 -     - - -       - - - -   - - -   - -   -   - - -   -    
|   | |     |o  | |       | |     | | |   |     | |       | |
   -     - -   -   -     -     -         - - -       - - -  
|   |   |o o o| |   | |     |   |     |   |   |   |     | | |
 - - - -   -       - - - -     - - - -         - - - -      
|     |o o  | |   |   | |   |   |     | | | | |         |   |
 -   -   - - - - -       - -   -   -     -       - -   - -  
|      o  |o o      | |   | |   | | | |     |   | |     |   |
 - - -   -     - - -   -     -         - - -   -   - - - - -
|   |o o|o o|o o    |       |       |   |   |   |     |     |
       -   - -     - - -   - -     - - -       - -   -     -
| | |o|  o o o|o|       |     | |   |     | |   |     | |   |
       - - -     - - - - - - - - - -   - -   -     -   -    
| | |o|o o o|o|o|     |                   |     |   | |   | |
         -         - -   - - - - -   -   - - - - - -     -  
| |  o|o o|o o|o|       |     |       | |             |   | |
 - -   -   - -   - - - -     -   - - - -   - -   - - -   -  
|o o|o o|o|o o|o o o o|   | |   |   |   |     |       | |   |
     -         - - -     - -   -   -       - - - -   -     -
|o|o o o|o|o|o o|   |o|         |     |   |       | |   |   |
   - - -     -         - -   - - - -   - -     - -     -   -
|o|   |  o|o o|o| |  o o o o o o o o|   |   |           |   |
     -     -     - - - - - -   -     - -   - -   - - - - - -
|o|   | |o o|o|o|o o o o o|     | |o| |   |     |           |
   -     -         - - -   - - - -       - - - -       - -  
|o|   |   |o o|o|o  |o o o|   |o o o| |     |     | | | |   |
     - -   - -     -   -     -   -     - -     - - - -   - -
|o| |     |o o o|o o|o|   |   |o|       |   |     |   |     |
       - -   - - -       - -     - - -     - -   -       -  
|o|   |o o o| |o o|o|o|       |o  |   | | |   |     | |   | |
   - -   - -           - - - -   -     -         - -   -    
|o o o o    |o o|o o|o|     |o o    |       | |     |     | |
   - - - - -   - - -   -   -   - - - - - - - - -   - - - -  
| |o o o|o o o|o o o o  |  o o|o o|o o  |           | |     |
     -     - -   - -   - -   -         -   - - - -     - - -
| |o|o o|o o o|o o  | |o o o|o o|o o|o o|   |   |o o  |     |
 -     - - -   -   - -   - -   - - - -   - -         -     -
|  o|o  |o o|o o|o o o o  |  o|o o o o|o  |   | |o|o o| |   |
       -     -   - - - - - -     - -     -   -     -   -   -
| |o|o o o|o  |o o|o o o o o|o o|o o o|o    |   |o  |o o|   |
 -   - - -   - -     - - -   - -   - -   - - - -   - -   -  
|  o o|o o|o|o o o|o o o|  o|o o|o o o|o o|o o o o|   |o o o|
   -           - - - -   -       - -   -     - - -     - -  
|   |o o|o|o o|o o|o o|o o|o|o|o|o o|o| |o|o o o  | |   | |o|
     - -   - -         -                   - -   -   -      
| |     |o o o o|o o|o o o|o o|o o|o o  |o o o o      |   |*|
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
https://ideone.com/ULVVnv
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!