马蹄铁

原题链接

思路：

• 使用深度优先搜索（DFS）。
  • 要使序列保持平衡，即形如 (((((....)))))，可设 p 为 ( 的数量，q 为 ) 的数量。
  • 特别注意：若起始字符为 )，则无论如何搜索都无法形成平衡序列，最大长度为 \(0\)。
  • 在搜索过程中，当 q != 0 时，若下一个字符为 (（如 (()(...），则当前路径不可能平衡，需剪枝。
  • 递归的每一层需记录当前位置坐标及当前的 p 与 q 值，并通过方向偏移量数组遍历相邻格子。
  • 当 p == q 时，即找到一条平衡路径，此时更新最大长度并返回，因为后续添加字符必然破坏平衡。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

char mp[N][N];
bool vis[N][N];

int n, res;

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int p, int q) {
    if (p == q) { // 已达到平衡
        res = max(res, p + q); // 更新最大长度
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) { // 在边界内且未访问
            if (q != 0 && mp[nx][ny] == '(') continue; // 遇到 `)` 后再出现 `(` 必不平衡，剪枝
            vis[nx][ny] = 1; // 标记为已访问
            if (mp[nx][ny] == '(') dfs(nx, ny, p + 1, q); // 遇到 `(` 则 p+1
            else dfs(nx, ny, p, q + 1); // 遇到 `)` 则 q+1
            vis[nx][ny] = 0; // 回溯，恢复状态
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> mp[i];
    if (mp[0][0] == ')') { // 若起点为 `)`，则无法形成有效平衡串
        cout << res << endl;
        return;
    }
    vis[0][0] = 1; // 标记起点为已访问
    dfs(0, 0, 1, 0); // 从起点开始搜索，初始 p=1, q=0
    cout << res << endl;
}

int main() {
    solve();
    return 0;
}