Generating maze is amazing! This algorithm is also widely used in lots of computer games.

Given a 2D array, generate a maze in it. There are several requirements of this maze:

- There are no circles in the maze, which means all roads in the maze lead to an dead end or to the exit.
- There are no wall blocks in the maze. Each wall is 1 unit in width, each road is also 1 unit in width.

For example,

//Following is not a legal maze, it contains wall block and circle road. //***********| //********* *| //******* *| //****** * *| //******* *| //***********|

A legal maze is something like,

// * * | // * | //** *| // ** | // * * *| // |

There is a simple and clear way to solve this problem, less than 100 lines of code.

Imaging an area full of rocks (wall) and you are a miner digging path through it.

When you are standing at a cell, you first randomly pick up an adjacent cell (up, down, left, right), try to dig it. When return, try another adjacent cell randomly, until all the 4 directions are tried.

The strategy for digging it with coordinate (i, j) or not is as follows:

- if this cell is out of boundary, do not dig it, return to last step
- if this cell is already digged, do not dig it again, return to last step
- if there are more than 1 of its 4 neighbor cells are digged, do not dig it, return to last step (since it will cause circles in path)
- else dig it. and move to this cell, jump to step 1.

Algorithm, a DFS approach:

```
map = [][] # initialize the map with full of walls
for each (i, j) cell in map:
DFS(i,j)
def DFS(i, j):
if i, j is out of boundary:
return
if (i,j) is visited:
return
if number of visited neighbors of (i, j) > 1:
return
mark cell as visited
for each neighbor (ni, nj) of cell(random order):
DFS(ni, nj)
```

C++ code is as follows. The complexity is O(n*n), n is the edge length of map.

#include "string" #include "vector" #include "unordered_map" #include "queue" #include "cstdlib" #include "ctime" #include <iostream> #include "algorithm" #include "stack" using namespace std; class Solution{ public: // Definition for singly-linked list. void maze(vector<vector<char>>& map){ //U unvisited, ' ' visited for (int i = 0; i < map.size(); ++i) { for (int j = 0; j < map[0].size(); ++j) { map[i][j] = '*'; } } _maze(map, 0, 0); } void showMaze(vector<vector<char>>& map){ for (int i = 0; i < map.size(); ++i) { for (int j = 0; j < map[0].size(); ++j) { cout<<map[i][j]; } cout<<endl; } } //Use DFS void _maze(vector<vector<char>>& map, int i, int j){ int direct[][2] = {{0,1}, {0,-1}, {-1,0}, {1,0}}; int visitOrder[] = {0,1,2,3}; //out of boundary if(i < 0 || j < 0 || i >= map.size() || j >= map[0].size()) return ; #ifdef DEBUG cout<<"("<<i<<", "<<j<<")"<<endl; #endif //visited, go back to the coming direction, return if(map[i][j] == ' ') return ; //some neightbors are visited in addition to the coming direction, return //this is to avoid circles in maze if(countVisitedNeighbor(map, i, j) > 1) return ; map[i][j] = ' '; // visited //shuffle the visitOrder shuffle(visitOrder, 4); for (int k = 0; k < 4; ++k) { int ni = i + direct[visitOrder[k]][0]; int nj = j + direct[visitOrder[k]][1]; _maze(map, ni, nj); } } int countVisitedNeighbor(vector<vector<char>>& map, int i, int j){ int direct[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; int count = 0; for (int k = 0; k < 4; ++k) { int ni = i + direct[k][0]; int nj = j + direct[k][1]; //out of boundary if(ni < 0 || nj < 0 || ni >= map.size() || nj >= map[0].size()) continue; if(map[ni][nj] == ' ') count++;//visited } return count; } void shuffle(int a[], int n){ for (int i = 0; i < n; ++i) { swap(a[i], a[rand() % n]); } } void swap(int & a, int &b){ int c = a; a = b; b = c; } }; int main(int argc, char const *argv[]) { Solution s; int height = 6; int width = 6; srand(time(0)); vector<char> row(width); vector<vector<char>> map; for (int i = 0; i < height; ++i) { map.push_back(row); } s.maze(map); s.showMaze(map); return 0; }