말굽

소 베시(Bessie)는 모든 균형 잡힌 괄호 문자열이 미적으로 아름답다고 생각하지만, 특히 베시가 "완벽하게" 균형 잡혔다고 부르는 문자열을 좋아한다. 이는 (들의 문자열 뒤에 같은 길이의 )들의 문자열이 이어지는 것이다. 예: (((()))).

어느 날 헛간을 걷던 베시는 바닥에서 N x N 격자로 놓인 말굽들을 발견했다. 각 말굽은 ( 또는 )처럼 보이도록 놓여 있다. 이 격자의 왼쪽 위 모서리에서 출발하여, 베시는 말굽들을 주우며 걸어 다니면서 주운 말굽들의 문자열이 완벽하게 균형 잡히게 만들고 싶어 한다. 베시가 얻을 수 있는 가장 긴 완벽하게 균형 잡힌 문자열의 길이를 계산하는 것을 도와주자.

각 단계에서 베시는 위, 아래, 왼쪽, 오른쪽으로 움직일 수 있다. 말굽이 있는 격자 칸으로만 이동할 수 있으며, 이동하면 그 말굽을 주우므로 같은 칸으로 다시 돌아갈 수 없다. 베시는 격자의 왼쪽 위 모서리의 말굽을 줍는 것으로 시작한다. 베시는 완벽하게 균형 잡힌 문자열을 이루는 말굽들의 나열만 줍는다.

첫째 줄: 정수 N (2 <= N <= 5).

둘째 줄부터 N+1번째 줄까지: 각 줄에 길이 N의 괄호 문자열이 주어진다. 이 N개의 줄이 모여 N x N 괄호 격자를 이룬다.

베시가 모을 수 있는 가장 긴 완벽하게 균형 잡힌 말굽 문자열의 길이. 베시가 균형 잡힌 말굽 문자열을 전혀 모을 수 없으면 (예를 들어 왼쪽 위 칸이 오른쪽 괄호라면) 0을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > November > Bronze