AcWing打卡-2005-马蹄铁

2005. 马蹄铁

题目描述

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

例如：

(((())))

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

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

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

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

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

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

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

输入格式

第一行包含整数 \(N\)。

接下来 \(N\) 行，每行包含一个长度为 \(N\) 的括号字符串，用来表示括号矩阵。

输出格式

输出她能得到的最长完全平衡括号字符串的长度。

如果无法得到完全平衡括号字符串（例如，左上角马蹄铁形如 )），则输出 00。

数据范围

\(2≤N≤5\)

输入样例：

4
(())
()((
(()(
))))

输出样例：

8

样例解释

贝茜的移动步骤如下：

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

TAGS: 回溯、dfs

这里题目说指出了，进入该区域后就会拿起那里的马蹄铁，无法回到原位置，所以，当我们已经拿到了)形状的马蹄铁时，就不能回溯了，只能继续拿)形状的马蹄铁，而其他时候则可以继续拿(或)形状的马蹄铁。

#include 
using namespace std;
const int N = 10;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int ans, n;
void dfs(int sx, int sy, int l, int r) //起点sx,sy,当前的左括号数l和右括号数r
{
    if (l == r && l != 0)
    {
        ans = max(ans, l + r);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = sx + dx[i];
        int ny = sy + dy[i];
        // 没有越界且没有被访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !st[nx][ny])
        {
            // 标记为已被访问过
            st[nx][ny] = true;
            // 已经捡过了)马蹄铁,只能继续找右马蹄铁
            if (r && g[nx][ny] == ')')
                dfs(nx, ny, l, r + 1);
            // 否则,左右马蹄铁都可以继续捡
            else if (!r && g[nx][ny] == '(')
                dfs(nx, ny, l + 1, r);
            else if (!r && g[nx][ny] == ')')
                dfs(nx, ny, l, r + 1);
            st[nx][ny] = false;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> g[i];
    }
    dfs(-1, 0, 0, 0);
    cout << ans << endl;
}