Матч 6, Скобочный лабиринт (BracketMaze)

Имеется куб размером 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)

Класс: BracketMaze

Метод: int properPaths(vector<string> maze, int n)

Ограничения: maze содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘(’, ‘)’, ‘.’, maze содержит в точности n³ букв после конкатенации, 1 £ n £ 13.

Вход. Массив строк maze, описывающий куб, и целое число n.

Выход. Количество путей из (1, 1, 1) в (n, n, n), которые описывают правильную скобочную структуру.

Пример входа

maze	n
"()()()()"	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).

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <numeric>

#include <memory>

#define MAX 1000000000

using namespace std;

char m[15][15][15];

int n, val[15][15][15][45];

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;

}

class BracketMaze

{

public:

int properPaths(vector<string> maze, int n)

{

int i, j, k, ptr, res;

string ALLmaze = accumulate(maze.begin(),maze.end(),string());

for(ptr = i = 0; i < n; i++) for(j = 0; j < n; j++) for(k = 0; k < n; k++)

m[i][j][k] = ALLmaze[ptr++];

memset(val,-1,sizeof(val));

::n = n; res = go(0,0,0,0);

return (res > MAX) ? -1 : res;

}

};