比赛 CSP2023-J模拟赛 评测结果 ATTTTTTTTT
题目名称 复制题目 最终得分 10
用户昵称 HXF 运行时间 9.044 s
代码语言 C++ 内存使用 7.53 MiB
提交时间 2023-10-18 20:23:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,m,maxx;
int xy[2][2]={{1,0},{0,1}};

bool mk[310][310];

char a[310][310];

map <string,bool> mp;

struct node{
	char c;
	int bian;
};

inline int read(){
	int t=0,f=1;
	register char c=getchar();
	while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
	while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
	return t*f;
}

void dfs(int x,int y,string s){
//	cout<<a[x][y]<<" "<<x<<" "<<y<<endl;
//	cout<<s<<endl;
	s+=a[x][y];
//	cout<<s<<endl;
	if(x==n&&y==m){
//		cout<<"YES"<<endl;
//		for(int l=0;l<s.size();l++) cout<<s[l];
//		cout<<endl;
		for(int i=0;i<s.size();i++){
			for(int j=1;j<=s.size();j++){
				string shi=s.substr(i,j);
//				if(s=="((())))") cout<<shi<<endl;
				if(mp[shi]) continue;
				mp[shi]=1;
				int ans=0;
				bool flagg=false;
				queue <node> q;
				for(int k=0;k<shi.size();k++){
					if(shi[k]=='(') q.push((node){shi[k],k});
					else{
						if(!q.size()||q.front().c!='('){
							flagg=true;
							break;
						}
						ans+=(k-q.front().bian);
						q.pop();
					}
				}
				if(flagg) continue;
				if(q.size()) continue;
				maxx=max(maxx,ans);
			}
		}
		return;
	}
	mk[x][y]=1;
	for(int i=0;i<=1;i++){
		int xx=x+xy[i][0],yy=y+xy[i][1];
		if(xx<1||xx>n||yy<1||yy>m||mk[xx][yy]) continue;
//		cout<<xx<<" "<<yy<<endl;
		dfs(xx,yy,s);
	}
	mk[x][y]=0;
}

int main(){
	freopen("copy.in","r",stdin);
	freopen("copy.out","w",stdout);
//	string ce="aa";
//	ce+='a';
//	cout<<ce;
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
//			cout<<a[i][j];
		}
	}
	string st="";
//	for(int i=0;i<st.size();i++) cout<<st[i];
	dfs(1,1,st);
	printf("%d",maxx);
	return 0;
}