We are given a maze which is a cube of NxNxN 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):
<expr> ::= empty-string | "("<expr>")" | <expr>"." | <expr><expr>
e.g., "(())", "....", ".()." and "().(.)" are valid parathesized expressions.
The maze is given in a String[] which, when concantenated, 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)
Given the String[] maze return an int representing the number of possible paths forming valid parenthesized expressions. If there are more than 1,000,000,000 paths, return -1 instead.
|