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:

1. There are no circles in the maze, which means all roads in the maze lead to an dead end or to the exit.
2. 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:

1. if this cell is out of boundary, do not dig it, return to last step
2. if this cell is already digged, do not dig it again, return to last step
3. 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)
4. 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;
}