Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
26674 | liuyile | 【BJ】T2 | C++ | 解答错误 | 0 | 5000 MS | 39512 KB | 2994 | 2024-02-21 21:30:35 |
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define mp make_pair #define fr first #define sc second const int MAXN=210,N=30,Maxn=200010,Mod=998244353,ie9=1000000000; int n,m,jc[N],dp[2][5000010],ans,a[MAXN][MAXN];char c[MAXN][MAXN],c2[MAXN][MAXN]; void swp(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ c2[j][i]=c[i][j]; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ c[i][j]=c2[i][j]; } } swap(n,m); } string sjz(int x){ string rt=""; for(int o=0;o<=m;o++){ rt+=('0'+x/jc[m-o]%3); } return rt; } void slv(){ scanf("%d%d",&n,&m);jc[0]=1; for(int i=1;i<=n;i++){ scanf("%s",c[i]+1); } if(m>n)swp(); for(int i=1;i<=N-5;i++)jc[i]=jc[i-1]*3; for(int i=0;i<=5000000;i++)dp[0][i]=dp[1][i]=ie9; for(int i=1;i<=n;i++,cout<<endl) for(int j=1;j<=m;j++) a[i][j]=c[i][j]-'0',cout<<a[i][j]; bool fl=0; dp[fl][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int p=0;p<jc[m+1];p++){ int up=p/jc[m-j]%3,rt=p/jc[m-j+1]%3,t=p; t-=up*jc[m-j]+rt*jc[m-j+1]; if(!a[i][j]||a[i][j]==2){ if((up==0)&&(rt==0)){ dp[fl^1][t+jc[m-j]]=min(dp[fl^1][t+jc[m-j]],dp[fl][p]); dp[fl^1][t+jc[m-j+1]]=min(dp[fl^1][t+jc[m-j+1]],dp[fl][p]); } else{ dp[fl^1][t+jc[m-j]*rt+jc[m-j+1]*up]=min(dp[fl^1][t+jc[m-j]*rt+jc[m-j+1]*up],dp[fl][p]); } dp[fl^1][t+jc[m-j]*2+jc[m-j+1]*2]=min(dp[fl^1][t+jc[m-j]*2+jc[m-j+1]*2],dp[fl][p]+1); } if(a[i][j]){ if(rt==1)continue; if(up==1)continue; dp[fl^1][t]=min(dp[fl^1][t],dp[fl][p]); } } for(int p=0;p<jc[m+1];p++){ dp[fl][p]=ie9; } fl^=1; } for(int p=0;p<jc[m+1];p++){ if(p%3!=1){ int t=p/3; dp[fl^1][t]=min(dp[fl^1][t],dp[fl][p]); } } for(int p=0;p<jc[m+1];p++){ dp[fl][p]=ie9; } fl^=1; // cout<<i<<endl; // for(int S=0;S<jc[m+1];S++) // if(dp[fl][S]<=n*m) // cout<<sjz(S)<<" "<<dp[fl][S]<<endl; // cout<<endl; } ans=ie9; for(int p=0;p<jc[m+1];p++){ bool cr=1; for(int i=0;i<m+1;i++){ if(p/jc[m-i]%3==1){cr=0;break;} } if(cr){ if(dp[fl][p]==4) // cout<<sjz(p)<<endl; ans=min(ans,dp[fl][p]); } } printf("%lld",ans); } signed main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); slv(); return 0; }