马蹄铁
题目描述:
尽管奶牛贝茜发现每个平衡括号字符串都很美观，但她特别喜欢被她称为“完全”平衡的括号字符串----一个由 ( 构成的字符串后接一个长度相同的 ) 构成的字符串。
例如：
( ( ( ( ) ) ) ) 有一天，当贝茜穿过牛棚时，她发现地面上有一个 N×N 的马蹄铁矩阵。每个马蹄铁的方向都看上去像 ( 或 )。
从矩阵的左上角开始，贝茜希望四处走动以拾起马蹄铁，使得她捡起的马蹄铁按顺序构成的括号字符串是完全平衡的。
请计算她能得到的最长完全平衡括号字符串的长度。
每一步中，贝茜可以沿上下左右四个方向移动。
她只能移动到包含马蹄铁的方格区域内，当她进入该区域时就会拿起那里的马蹄铁，并无法再次回到该位置（因为该位置没有马蹄铁了）。
她首先拿起的是左上角的马蹄铁。
由于她拿起的马蹄铁要形成一个完全平衡的字符串，因此她可能无法将所有马蹄铁都拿起来。
输入格式:
第一行包含整数 N。
接下来 N 行，每行包含一个长度为 N 的括号字符串，用来表示括号矩阵。
输出格式:
输出她能得到的最长完全平衡括号字符串的长度。
如果无法得到完全平衡括号字符串（ 例如，左上角马蹄铁形如 ）），则输出 0。
数据范围:
2 ≤ N ≤ 5
样例输入:
4 (()) ()(( (()( ))))
样例输出:
8
提示:
贝茜的移动步骤如下：
1())
2)((
345(
876)空间限制: 256MB
来源: USACO 2012 November Contest Bronze