马蹄铁

题目

链接：2005. 马蹄铁 - AcWing题库

尽管奶牛贝茜发现每个平衡括号字符串都很美观，但她特别喜欢被她称为“完全”平衡的括号字符串——一个由 ( 构成的字符串后接一个长度相同的 ) 构成的字符串。

例如：

(((())))

有一天，当贝茜穿过牛棚时，她发现地面上有一个 N×N 的马蹄铁矩阵。每个马蹄铁的方向都看上去像 ( 或 )。

从矩阵的左上角开始，贝茜希望四处走动以拾起马蹄铁，使得她捡起的马蹄铁按顺序构成的括号字符串是完全平衡的。

请计算她能得到的最长完全平衡括号字符串的长度。

每一步中，贝茜可以沿上下左右四个方向移动。

她只能移动到包含马蹄铁的方格区域内，当她进入该区域时就会拿起那里的马蹄铁，并无法再次回到该位置（因为该位置没有马蹄铁了）。

她首先拿起的是左上角的马蹄铁。

由于她拿起的马蹄铁要形成一个完全平衡的字符串，因此她可能无法将所有马蹄铁都拿起来。

代码

import java.util.*;

public class Main {
    static int n;
    static char[][] s = new char[10][10];
    static int ans = 0;
    static int[] xx = {0, 0, 1, -1};
    static int[] yy = {1, -1, 0, 0};
    static boolean[][] f = new boolean[10][10];
    public static void bfs(int x, int y, int l, int r)
    {
        f[x][y] = true;
        if(l == r)
        {
            ans = Math.max(ans, l + r);
            f[x][y] = false;
            return;
        }
        for(int i = 0; i < 4; i ++)
        {
            int x1 = x + xx[i], y1 = y + yy[i];
            if(0 < x1 && x1 <= n && 0 < y1 && y1 <= n && !f[x1][y1])
            {
                if(s[x][y] == ')' && s[x1][y1] == '(')
                    continue;
                if(s[x1][y1] == ')')
                    bfs(x1, y1, l, r + 1);
                else
                    bfs(x1, y1, l + 1, r);
            }
        }
        f[x][y] = false;
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            String ss;
            ss = inScanner.next();
            for(int j = 0; j < n; j ++)
            {
                s[i][j + 1] = ss.charAt(j);
            }
        }
        inScanner.close();
        if(s[1][1] == '(')
            bfs(1, 1, 1, 0);
        System.out.println(ans);
    }
}
/*
4
(())
()((
(()(
))))
*/