题目链接
https://www.acwing.com/problem/content/2007/
思路
由于这个题目数据范围很小,所以我们可以进行暴力搜索,从左上角1,1点开始回溯搜索,注意的是,由于要形成题目中括号的格式,所以我们能发现左括号能走到左括号或者右括号,而右括号只能走到右括号
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 10;
int n;
char mp[N][N];
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
bool check(int x,int y){
if(x >= 1 && x <= n && y >= 1 && y<= n) {
return true;
}
return false;
}
bool vis[N][N];
int ans = 0;
map<string,bool> viss;
bool is_ok(string ch){//判断是否为正确的括号序列
int len = ch.size();
if(len % 2) return false;
for(int i = 0;i < len/2; ++i) {
if(ch[i] =='(' && ch[len-i-1] == ')') continue;
return false;
}
return true;
}
void dfs(int x,int y,string ch){//回溯暴力搜索
if(is_ok(ch)){
// puts("-----begin-----");
// cout<<ch<<endl;
// puts("-----end-----");
ans = max(ans,(int)ch.length());
return;
}
for(int i = 0;i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if(check(nx,ny) && vis[nx][ny] == false) {
if(mp[x][y] == '('){//左括号可以到右括号,也可以到左括号
vis[nx][ny] = true;
ch.push_back(mp[nx][ny]);
dfs(nx,ny,ch);
vis[nx][ny] = false;
ch.pop_back();
}
else{
if(mp[nx][ny] == ')') {//右括号只能到左括号
vis[nx][ny] = true;
ch.push_back(mp[nx][ny]);
dfs(nx,ny,ch);
vis[nx][ny] = false;
ch.pop_back();
}
}
}
}
}
int main()
{
cin>>n;
for(int i = 1;i <= n; ++i) {
for(int j = 1;j <= n; ++j) {
cin>>mp[i][j];
}
}
string ch="";
ch += mp[1][1];
vis[1][1] = true;
dfs(1,1,ch);
cout<<ans<<endl;
return 0;
}