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 existone and only one path between them. (Randomlymeans 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

Solution: 因为路和墙宽度为1，所以每次DFS走2步。注意如何shuffle

  public int[][] maze(int n) {
    int[][] maze = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        maze[i][j] = 1;
      }
    }
    maze[0][0] = 0;
    generate(maze, 0, 0);
    return maze;
  }
  private void generate(int[][] maze, int x, int y) {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    shuffle(dx, dy);
    for (int i = 0; i < 4; i++) {
      if (x + dx[i] * 2 >= 0 && x + dx[i] * 2 < maze.length && y + dy[i] * 2 >= 0 
        && y + dy[i] * 2 < maze[0].length && maze[x + dx[i] * 2][y + dy[i] * 2] == 1) {
          maze[x + dx[i] * 2][y + dy[i] * 2] = 0;
          maze[x + dx[i]][y + dy[i]] = 0;
          generate(maze, x + dx[i] * 2, y + dy[i] * 2);
        }
    }
  }
  private void shuffle(int[] dx, int[] dy) {
    for (int i = 0; i < dx.length - 1; i++) {
      int offset = (int) (Math.random() * (dx.length - i));
      int temp = dx[i];
      dx[i] = dx[i + offset];
      dx[i + offset] = temp;
      temp = dy[i];
      dy[i] = dy[i + offset];
      dy[i + offset] = temp;
    }
  }