Vintage computer game Rogue features set of small mazes -
levels of the dungeon, into which the hero should descent. These mazes are built randomly based on a layout
of 3 by 3 cells, connected with passages. The image above demonstrates typical level map (when completely traversed
and revealed).
Passages can only connect cells adjacent vertically or horizontally. I.e. they are like lines in 3 by 3 grid.
This gives us idea for a small problem. Suppose the base layout is slightly larger, 4 by 4 but several cells
of them are absent (they do not exist, no passages may lead to them). How many different mazes could be constructed
with minimal number of passages between cells allowing connectivity between all cells.
For example, if we keep with original smaller-size layout 3 by 3 and the central cell is absent, this leaves
8 cells in a form of ring. It is easy to see there exist 8 different "minimal" mazes for this layout: pick
any pair of adjacent cells and draw an "almost complete" ring of passages, like this:
O--O--O 0--1--2
| |
O O or, enumerating cells 3 5
| | | |
O--O--O 6--7--8
In this case we pick the pair of cells #2 and #5 and draw a maze in a form of letter G between them. It
is easy to see all other mazes on this cell layout will be just rotations and flipping of this one. The maze
with full "circle" is not counted since it is not minimal (any passage could be removed and still the maze
is well-connected).
Note that we introduce numbering of cells, starting from 0 and filling row by row (absent cells retain their
numbers - in this case cell 4 is absent). In other words:
cell_number = row * width + column (with rows and columns 0-based)
You can check that in case of cell #3 absent there are total of 15 mazes. Same as if two cells #0 and #2
are absent instead.
Input data consist of 2 or 3 values - numbers of cells missing from the 4 by 4 grid.
Answer should give the only value - number of "minimal" mazes which could be built with the given layout.
Example
input:
0 4
answer:
8948
P.S. Checker will carefully avoid offering layouts in which no connected maze could be built.