페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3798

말굽 (Horseshoes) 1초 128MB

문제

배씨는 균형 잡힌 괄호 문자열을 미학적으로 매우 매력적으로 생각하지만, 특히 완벽하게 균형 잡힌 문자열이라고 부르는 문자열을 특히 좋아한다. 이 문자열은 ('로 시작하는 문자열 뒤에 길이가 같은 )' 문자열이 따르는 형태이다. 예를 들어 "(((())))"와 같은 문자열을 의미한다.

어느 날 헛간을 거니던 중, 배씨는 N \times N 크기의 바닥에 놓여진 말굽들을 발견한다. 각 말굽은 ( 또는 ) 중 하나의 모양으로 되어 있다. 이 바닥의 좌측 상단 모서리에서 시작해서, 배씨는 말굽을 따라 걸어가며 말굽을 주워 문자열을 만들고 싶어한다. 선택한 문자열이 완벽하게 균형 잡힌 문자열이 되도록 말굽을 선택해야 한다면, 배씨가 얻을 수 있는 가장 긴 완벽하게 균형 잡힌 문자열의 길이가 얼마인지 알아보자.

각 단계에서 배씨는 위, 아래, 왼쪽 또는 오른쪽으로 움직일 수 있다. 현 위치에 말굽이 있는 경우에만 이동할 수 있으며, 그렇게 할 경우 말굽을 집어 올려 해당 위치로 다시 돌아갈 수 없다 (이제 그 위치에는 말굽이 없기 때문이다). 배씨는 바닥의 좌측 상단 모서리에 있는 말굽을 집어 올리며 시작하여 완벽하게 균형 잡힌 문자열을 형성하는 일련의 말굽만을 집어 올리며, 따라서 바닥의 모든 말굽을 집어 올릴 수 없을 수도 있다.


입력

* Line 1: An integer N (2 <= N <= 5).

* Lines2..N+1: Each line contains a string of parentheses of length N. Collectively, these N lines describe an N \times N grid of parentheses.


출력

* Line 1: The length of the longest perfectly balanced string of horseshoes Bessie can collect. If Bessie cannot collect any balanced string of horseshoes (e.g., if the upper-left square is a right parenthesis), output 0.


예제1

입력
4
(())
()((
(()(
))))
출력
8

The sequence of steps Bessie takes to obtain a balanced string of length 8 is as follows:

1())
2)((
345(
876)

출처

USACO 2012 November Bronze

역링크 공식 문제집만