WxH grid, how many possible mazes are there?
Things you know about the maze:
- The grid is exactly
Hsquares high and
- There are three types of squares: Start, Finish, and Empty. Your maze must contain exactly 1 Start and 1 Finish, and all remaining squares are Empty.
- There are walls surrounding the entire maze.
- Walls can exist on the edge between any two squares, unless it breaks the below rule:
- There must exist a path from the Start square to the Finish square.
Therefore, given two numbers,
H, you must return a single number representing the number of possible square/wall configurations. You are guaranteed that
W*H > 1
For example, the
2x2 maze has exactly
100 different possible configurations.
This is a code-golf so the shortest answer wins!