比赛 CSP2023-J模拟赛 评测结果 ATTTTTTTTT
题目名称 复制题目 最终得分 10
用户昵称 HXF 运行时间 9.044 s
代码语言 C++ 内存使用 7.53 MiB
提交时间 2023-10-18 20:23:44
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,maxx;
  4. int xy[2][2]={{1,0},{0,1}};
  5.  
  6. bool mk[310][310];
  7.  
  8. char a[310][310];
  9.  
  10. map <string,bool> mp;
  11.  
  12. struct node{
  13. char c;
  14. int bian;
  15. };
  16.  
  17. inline int read(){
  18. int t=0,f=1;
  19. register char c=getchar();
  20. while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
  21. while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
  22. return t*f;
  23. }
  24.  
  25. void dfs(int x,int y,string s){
  26. // cout<<a[x][y]<<" "<<x<<" "<<y<<endl;
  27. // cout<<s<<endl;
  28. s+=a[x][y];
  29. // cout<<s<<endl;
  30. if(x==n&&y==m){
  31. // cout<<"YES"<<endl;
  32. // for(int l=0;l<s.size();l++) cout<<s[l];
  33. // cout<<endl;
  34. for(int i=0;i<s.size();i++){
  35. for(int j=1;j<=s.size();j++){
  36. string shi=s.substr(i,j);
  37. // if(s=="((())))") cout<<shi<<endl;
  38. if(mp[shi]) continue;
  39. mp[shi]=1;
  40. int ans=0;
  41. bool flagg=false;
  42. queue <node> q;
  43. for(int k=0;k<shi.size();k++){
  44. if(shi[k]=='(') q.push((node){shi[k],k});
  45. else{
  46. if(!q.size()||q.front().c!='('){
  47. flagg=true;
  48. break;
  49. }
  50. ans+=(k-q.front().bian);
  51. q.pop();
  52. }
  53. }
  54. if(flagg) continue;
  55. if(q.size()) continue;
  56. maxx=max(maxx,ans);
  57. }
  58. }
  59. return;
  60. }
  61. mk[x][y]=1;
  62. for(int i=0;i<=1;i++){
  63. int xx=x+xy[i][0],yy=y+xy[i][1];
  64. if(xx<1||xx>n||yy<1||yy>m||mk[xx][yy]) continue;
  65. // cout<<xx<<" "<<yy<<endl;
  66. dfs(xx,yy,s);
  67. }
  68. mk[x][y]=0;
  69. }
  70.  
  71. int main(){
  72. freopen("copy.in","r",stdin);
  73. freopen("copy.out","w",stdout);
  74. // string ce="aa";
  75. // ce+='a';
  76. // cout<<ce;
  77. n=read(),m=read();
  78. for(int i=1;i<=n;i++){
  79. for(int j=1;j<=m;j++){
  80. cin>>a[i][j];
  81. // cout<<a[i][j];
  82. }
  83. }
  84. string st="";
  85. // for(int i=0;i<st.size();i++) cout<<st[i];
  86. dfs(1,1,st);
  87. printf("%d",maxx);
  88. return 0;
  89. }
  90.