暴力求长度为 len 时, 以 i,j 为左上角的旗子的数量
不剪枝的话复杂度是 n*n*m*n, 必定超时
两个可以剪枝的地方: 如果格子 [i,j] 可以作为长度为 len 的旗子的左上角, 那么其必定不可以作为长度 > len 的旗子的左上角
同理, 如果格子 [i,j] 为左上角不可以组成长度为 len 的旗子, 并且是因为 len 行内有不同色块导致的, 那么显然这个格子作为左上角也不可以作为长度 > len 的旗子的左上角
用 f[i][j]标记一下即可
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 1005;
- int n,m,f[maxn][maxn];
- char mp[maxn][maxn];
- int main(){
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- scanf("%s",mp[i]+1);
- int ans=0;
- for(int len=1;len*3<=n;len++){
- for(int i=1;i+len*3-1<=n;i++){
- char la,lb,lc;
- int sum=0,cnt=0;
- for(int j=1;j<=m;j++){
- if(f[i][j]){cnt=0;continue;}
- char a=mp[i][j],b=mp[i+len][j],c=mp[i+len*2][j];
- if(a==b || b==c){
- la=a;lb=b;lc=c;
- cnt=0;continue;
- }
- int flag=0;
- for(int k=1;k<len;k++)
- if(mp[i+k][j]!=a || mp[i+len+k][j]!=b || mp[i+len*2+k][j]!=c){
- f[i][j]=1;
- la=a;lb=b;lc=c;
- cnt=0;flag=1;break;
- }
- if(flag)continue;
- if(j!=1 && (la!=a || lb!=b || lc!=c))cnt=1;
- else cnt++;
- f[i][j]=1;
- sum+=cnt;
- la=a;lb=b;lc=c;
- }
- ans+=sum;
- }
- }
- cout<<ans<<'\n';
- }
来源: http://www.bubuko.com/infodetail-3101093.html