本文最后更新于 699 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
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 l = x + dx[i], r = y + dy[i]; |
| if(l >= 0 && l < n && r >= 0 && r < n && !vis[l][r]){ |
| if(q != 0 && mp[l][r] == '(') continue; |
| vis[l][r] = 1; |
| if(mp[l][r] == '(') dfs(l, r, p + 1, q); |
| else dfs(l, r, p, q + 1); |
| vis[l][r] = 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); |
| cout << res << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |