题目描述：
尽管奶牛贝茜发现每个平衡括号字符串都很美观，但她特别喜欢被她称为“完全”平衡的括号字符串——一个由 ( 构成的字符串后接一个长度相同的 ) 构成的字符串。
例如：
有一天，当贝茜穿过牛棚时，她发现地面上有一个 $ N\times N $ 的马蹄铁矩阵。每个马蹄铁的方向都看上去像 ( 或 )。
从矩阵的左上角开始，贝茜希望四处走动以拾起马蹄铁，使得她捡起的马蹄铁按顺序构成的括号字符串是完全平衡的。
请计算她能得到的最长完全平衡括号字符串的长度。
每一步中，贝茜可以沿上下左右四个方向移动。
她只能移动到包含马蹄铁的方格区域内，当她进入该区域时就会拿起那里的马蹄铁，并无法再次回到该位置（因为该位置没有马蹄铁了）。
她首先拿起的是左上角的马蹄铁。
由于她拿起的马蹄铁要形成一个完全平衡的字符串，因此她可能无法将所有马蹄铁都拿起来。
输入格式
第一行包含整数 $ N $ 。
接下来 $ N $ 行，每行包含一个长度为 $ N $ 的括号字符串，用来表示括号矩阵。
输出格式
输出她能得到的最长完全平衡括号字符串的长度。
如果无法得到完全平衡括号字符串（例如，左上角马蹄铁形如 )），则输出 $ 0 $ 。
数据范围
$ 2 \le N \le 5 $
输入样例：
输出样例：
样例解释
贝茜的移动步骤如下：
题解：
注意需要进行回溯，在 dfs 之前进行操作，在 dfs 之后取消操作。有的操作可能是标记，有的可能是取下。例如分为互质组中是加入 vector，从 vector 中删除。这里是标记取过，取消标记。
注意顺序，r 不为 $ 0 $ 的时候只能 l++。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
char g[maxn][maxn];
bool vis[maxn][maxn];
int ans;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int l, int r)
{
if (l > 0 && l == r)
{
ans = max(ans, l + r);
return;
}
for (int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if (newx < 0 || newx >= n || newy < 0 || newy >= n || vis[newx][newy])
continue;
if (r != 0 && g[newx][newy] == '(')
continue;
vis[newx][newy] = true;
if (g[newx][newy] == '(')
{
dfs(newx, newy, l + 1, r);
}
else
{
dfs(newx, newy, l, r + 1);
}
vis[newx][newy] = false;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> g[i];
}
if (g[0][0] == ')')
puts("0");
else
{
vis[0][0] = true;
dfs(0, 0, 1, 0);
cout << ans << endl;
}
return 0;
}
|