Еще Беси уважает "совершенно сбалансированные строки", в которых за строкой из левых скобок следует строка их правых скобок такой же длины.
(((())))
Имеется двумерный массив из N*N символов ( и ). Начиная с левого верхнего угла массива нужно пройти, выбирая символы так, чтобы построенная строка была совершенно сбалансированной и имела максимальную длину.
На каждом шагу можно двигаться вверх, вниз, влево или вправо, но нельзя заходить в одну и ту же клетку более одного раза. Можно зайти не во все клетки.
PROBLEM NAME: hshoe
Формат входных данных
* Строка 1: Целое число N (2 <= N <= 5).
* Строки 2..N+1: Каждая строка содержит строку из N скобок. Все вместе эти строки описывают решетку N*N.
Формат выходных данных
* Line 1:Длина наибольшей совершенно сбалансированной строки. Если Беси не может построить совершенно сбалансированную строку например, если левый верхний угол содержит символ )., то выведите 0.
Примечание
Последовательность шагов, которую нужно выполнить, чтобы получит ответ 8 такова: 1()) 2)(( 345( 876)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
(())
()((
(()(
))))
|
8
|