Generate Random Maze (Laicode 218)
https://app.laicode.io/app/problem/218
“Description
Randomly generate a maze of size N * N (where N = 2K + 1) whose corridor and wall’s width are both 1 cell. For each pair of cells on the corridor, there must exist one and only one path between them. (Randomly means that the solution is generated randomly, and whenever the program is executed, the solution can be different.). The wall is denoted by 1 in the matrix and corridor is denoted by 0.
Assumptions
N = 2K + 1 and K >= 0
the top left corner must be corridor
there should be as many corridor cells as possible
for each pair of cells on the corridor, there must exist one and only one path between them
Examples
N = 5, one possible maze generated is
0 0 0 1 0
1 1 0 1 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
”
这道题的难点在于给这个问题建模， 不在于算法。算法本身就是个基本的图遍历的问题 + shuffle遍历顺序。
为了避免产生厚度为2的墙或厚度为2的走廓， 我们的graph node是地图上偶数行和偶数列上的点。其他的点不是我们的Graph Node!!
这个问题就是从起始点出发遍历所有graph node的过程，要避免环。所以要用visited来标记，但是这个visited其实可以和maze本身结合在一起，所以实际操作中也不需要visited。
为了随机性，我们shuffle遍历的方向。
public class Solution {
int[][] OFFSETS;
int n;
int[] dirs;
Random random;
public int[][] maze(int n) {
OFFSETS = new int[][]{{0, 2}, {0, -2}, {2, 0}, {-2, 0}};
this.n = n;
random = new Random();
dirs = new int[]{0, 1, 2, 3};
//build graph
// what is a graph node here??
// every node at even row and even col are the graphNode
// we need to traverse all nodes
int[][] mz = new int[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
mz[r][c] = 1;
}
}
mz[0][0] = 0;
dfs(mz, 0, 0);
return mz;
}
private void dfs(int[][] maze, int r, int c) {
int[] array = shuffle();
for (int dir : array) {
int[] os = OFFSETS[dir];
int nr = r + os[0];
int nc = c + os[1];
if (nr < 0 || nc < 0 || nr >= n || nc >= n
|| maze[nr][nc] == 0) continue;
maze[r + os[0] / 2][c + os[1] / 2] = 0;
maze[nr][nc] = 0;
dfs(maze, nr, nc);
}
}
private int[] shuffle(){
for (int i = 0; i < 3; i++) {
int next = random.nextInt(4 - i);
swap(dirs, i, i + next);
}
return Arrays.copyOfRange(dirs, 0, 4);
}
private void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
