Bracket Maze
We are given a maze which is a cube of n * n * n cells. We start at (1,1,1) and we move to (n,n,n), in each move visiting one of the three adjacents cells in the positive x, y or z directions. Each cell of the maze contains either a '(', ')' or '.'. A path is the sequence of cells visited during the journey. We intend to find the number of such paths that produce a valid parenthesized expression.
Periods can occur freely in an expression, and must be ignored while checking if an expression is properly paranthesized or not. A paranthesized expression is said to be valid only if it adheres to the following grammar (quotes for clarity):
::= empty-string | "("")" | "." |
e.g., "(())", "....", ".()." and "().(.)" are valid parathesized expressions.
The maze is given in a string which represents the cube encoded in the following manner. The characters of maze correspond to the following cube coordinates, in order:
(1,1,1), (1,1,2), ..., (1,1,n), (1,2,1), (1,2,2), ..., (1,n,n), (2,1,1), ..., (n,n,n)
Input
Each line contains the positive integer n (1 ≤ n ≤ 13) and the string maze that consists of exactly n^3 characters.
Output
For each test case print in a separate line the number of paths from (1, 1, 1) to (n, n, n) that produce a valid parenthesized expression. If there are more than 1,000,000,000 paths, print -1 instead.