Задачи
Скобочный лабиринт
Скобочный лабиринт
Имеется куб размером \textbf{n} * \textbf{n} * \textbf{n}. Начиная движение из ячейки (\textbf{1}, \textbf{1}, \textbf{1}), необходимо прийти в (\textbf{n}, \textbf{n}, \textbf{n}). Из каждой ячейки можно двигаться в соседнюю по направлению возрастания \textbf{x}, \textbf{y} или \textbf{z} координаты. Каждая ячейка куба содержит один из символов: ‘(‘, ‘)’ или ‘.’. Путем будем называть последовательность ячеек, посещаемых при движении. Необходимо найти количество путей из (\textbf{1}, \textbf{1}, \textbf{1}) в (\textbf{n}, \textbf{n}, \textbf{n}), которые описывают правильную скобочную структуру.
Правильной скобочной структурой называется выражение, порождающееся грамматикой:
::= empty-string | "("")" | "." |
Выражение может содержать произвольное количество точек, которые не учитываются при определении его правильности. Например, строки "(())", "....", ".()." и "().(.)" являются правильными скобочными структурами.
Символы строки \textbf{maze} соответствуют координатам ячеек куба следующим образом:
(\textbf{1}, \textbf{1}, \textbf{1}), (\textbf{1}, \textbf{1}, \textbf{2}), ..., (\textbf{1}, \textbf{1}, \textbf{n}), (\textbf{1}, \textbf{2}, \textbf{1}), (\textbf{1}, \textbf{2}, \textbf{2}), ...,
(\textbf{1}, \textbf{n}, \textbf{n}), (\textbf{2}, \textbf{1}, \textbf{1}), ..., (\textbf{n}, \textbf{n}, \textbf{n})
\InputFile
Каждая строка содержит натуральное число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{13}) и строку \textbf{maze}, которая состоит в точности из \textbf{n^3} символов.
\OutputFile
Для каждого теста в отдельной строке вывести количество путей из (\textbf{1}, \textbf{1}, \textbf{1}) в (\textbf{n}, \textbf{n}, \textbf{n}), которые описывают правильную скобочную структуру. Если путей больше \textbf{1,000,000,000}, то выведите \textbf{-1}.
Входные данные #1
2 ()()()() 3 ........................... 2 )()()()(
Выходные данные #1
2 90 0