Имеется куб размером n * n
* n. Начиная движение из ячейки (1,
1, 1), необходимо прийти в (n, n, n).
Из каждой ячейки можно двигаться в соседнюю по направлению возрастания x, y
или z координаты. Каждая ячейка куба
содержит один из символов: ‘(‘, ‘)’ или ‘.’. Путем будем называть
последовательность ячеек, посещаемых при движении. Необходимо найти количество
путей из (1, 1, 1) в (n, n, n),
которые описывают правильную скобочную структуру.
Правильной скобочной структурой называется выражение,
порождающееся грамматикой:
<expr>
::= empty-string | "("<expr>")"
| <expr>"." | <expr><expr>
Выражение может содержать произвольное количество точек,
которые не учитываются при определении его правильности. Например, строки
"(())", "....", ".()." и "().(.)"
являются правильными скобочными структурами.
Символы строки maze
соответствуют координатам ячеек куба следующим образом:
(1, 1, 1), (1, 1, 2), ..., (1, 1, n), (1, 2, 1), (1, 2, 2), ..., (1, n, n),
(2, 1, 1), ..., (n, n, n)
Вход. Каждая строка содержит натуральное число n (1 ≤ n ≤ 13) и строку maze,
которая состоит в точности из n3
символов.
Выход. Для каждого
теста в отдельной строке вывести количество путей из (1, 1, 1) в (n, n,
n), которые описывают правильную
скобочную структуру. Если количество путей больше 1000000000, то вывести -1.
|
Пример
входа |
Пример
выхода |
|
2 ()()()() 3
........................... 2 )()()()( |
2 90 0 |
РЕШЕНИЕ
динамическое программирование
Анализ алгоритма
Рассмотрим
алгоритм, проверяющий, содержит ли данная строка правильную скобочную структуру.
Инициализируем переменную x нулем.
Будем двигаться по строке слева направо. При встрече открывающей скобки будем
увеличивать x на 1, при встрече
закрывающей скобки – уменьшать x на
1. Если по завершению обработки строки x
= 0, а в процессе вычислений x
никогда не становился отрицательным, то строка описывает правильную скобочную
структуру.
Занесем в трехмерный массив m информацию о кубе, хранящуюся в
массиве строк maze. Элемент val[i][j][k][x] будет хранить количество путей из (i, j,
k) в (n – 1, n – 1, n – 1), для которых x открытых скобок еще не закрыты. Поскольку индексы массивов в Си
нумеруются с нуля, то интересующие нас пути идут из ячейки (0, 0, 0) в (n – 1, n – 1, n – 1).
Будем
моделировать перебор всех путей: из ячейки (i,
j, k) можно пойти в (i + 1, j, k),
в (i, j + 1, k) или в (i, j,
k + 1). Поэтому количество искомых
путей из (i, j, k) равно сумме числа
путей из этих трех клеток. Если текущее количество путей на любом этапе
вычислений станет больше 1000000000, то прерываем процесс дальнейшего поиска:
ответом задачи будет -1 как требуется в условии задачи.
Функция go(i, j,
k, x) вычисляет значение val[i][j][k][x]. Когда (i, j, k) = (n – 1, n – 1, n – 1), то смотрим на значение х: если оно равно 0 (все открывающиеся
скобки закрыты), то к общей сумме путей прибавляем 1. Если на каком-то этапе
вычислений один из аргументов i, j, k
выходит за пределы 1 £ i, j,
k £ n – 1 или x < 0, то возвращаем 0 (пройденный
путь не может быть префиксом правильного скобочного выражения).
Ответом будет
значение val[0][0][0][0], вычисленное вызовом go(0, 0, 0, 0).
Реализация алгоритма
Определим
необходимые массивы и переменные.
#define MAX 1000000000
char m[15][15][15];
char maze[4000];
int n, res, val[15][15][15][45];
Функция go(i, j, k,
x) вычисляет значение val[i][j][k][x].
Если на каком-то этапе вычислений текущее количество путей temp станет больше MAX = 1000000000, то temp присваиваем значение MAX + 1. В дальнейшем это будет означать,
что ответом на текущий тест будет -1.
int go(int i,int j, int k,int x)
{
int &temp = val[i][j][k][x];
if (temp != -1) return
temp;
if ((i >= n) || (j >= n) || (k >= n)) return 0;
if (m[i][j][k] == '(')
x++;
if (m[i][j][k] == ')')
x--;
if (x < 0) return
0;
if ((i == n - 1) && (j == n - 1) &&
(k == n - 1)) return (x == 0);
temp = go(i+1,j,k,x); if (temp > MAX) return
temp = MAX + 1;
temp += go(i,j+1,k,x); if (temp >
MAX) return temp = MAX + 1;
temp += go(i,j,k+1,x); if (temp >
MAX) return temp = MAX + 1;
return temp;
}
Информацию о лабиринте переносим из строки maze в трехмерный массив m.
Инициализируем ячейки массива val значениями -1. Возвращаем искомое количество
путей, которое будет записано в val[0][0][0][0]. Его вычисление достигается
вызовом go(0, 0, 0, 0).
int properPaths()
{
int i, j, k, ptr, res;
for(ptr = i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++)
m[i][j][k] = maze[ptr++];
memset(val,-1,sizeof(val));
res = go(0,0,0,0);
return (res > MAX) ? -1 : res;
}
Основная часть программы.
while(scanf("%d %s",&n,&maze)
== 2)
{
res = properPaths();
printf("%d\n",res);
}