FillInTheMaze

There is a very simple way to draw mazes using ASCII characters. One sample maze with three entrances is shown below. (The '#'s represent walls, the '.'s represent empty cells.)

#######.#####
......#.#...#
#.###.#.#.#.#
#.#.......#.#
#.#######.#.#
#.......#.#.#
#########.###

Here is the construction of such a maze in more detail. Let's take a look at an unfinished maze that has walls everywhere.

#############
#.#.#.#.#.#.#
#############
#.#.#.#.#.#.#
#############
#.#.#.#.#.#.#
#############

Rows and columns of the bitmap are numbered starting from 0 in the top left corner. Notice that the cells with both coordinates odd are still empty. These cells are called rooms. The cells that share a side with a room are called hallways and the remaining cells are called pillars. Hence, pillars have both coordinates even. Pillars will always be walls. Some hallways will eventually be empty while others will be walls.

You are given ints R, C, and X. Your task is to design any maze with R rows and C columns of rooms (that is, 2R+1 rows of characters, each containing 2C+1 characters). The maze must have the following additional properties:

• Each room must be reachable from each other room, without leaving the maze.
• There have to be exactly X exits (i.e., empty hallways on the boundary of the maze).
• The total number of wall cells ('#' characters) must be maximized.

Return a String[] with the resulting maze. Any valid answer will be accepted.