thupc B 题求调
  • 板块学术版
  • 楼主wukaichen888
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/12/15 16:19
  • 上次更新2024/12/15 19:30:56
查看原帖
thupc B 题求调
723238
wukaichen888楼主2024/12/15 16:19
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=2005,inf=1e9;
int n,m,d;
int b[N][N],U[N][N],D[N][N],ans;
int bl,br,bu,bd;
char s[N][N],t[N][N];
void check(int x1,int x2,int y1,int y2){
	if(bl+1>=y1-d)
		if(bu+1>=x1)
			if(br-1<=y2)
				if(bd-1<=x2)
					ans=max(ans,(x2-x1+1)*(y2-y1+1));
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++) scanf("%s",t[i]+1);
	bd=n+1,br=m+1;
	for(int i=1,flag=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			if(s[i][j]!=t[i][j]){flag=0;break;}
		if(!flag) break;bu=i;}
	for(int i=n,flag=1;i>=1;i--){
		for(int j=1;j<=m;j++)
			if(s[i][j]!=t[i][j]){flag=0;break;}
		if(!flag) break;bd=i;}
	
	for(int j=1,flag=1;j<=m;j++){
		for(int i=1;i<=n;i++)
			if(s[i][j]!=t[i][j]){flag=0;break;}
		if(!flag) break;bl=j;}
	for(int j=m,flag=1;j>=1;j--){
		for(int i=1;i<=n;i++)
			if(s[i][j]!=t[i][j]){flag=0;break;}
		if(!flag) break;br=j;}
	
	for(d=1;d<m;d++){
		ans=-1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(j<=d) b[i][j]=0;
				else{
					if(s[i][j]==t[i][j-d]) b[i][j]=1;
					else b[i][j]=0;
				}
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(b[i][j]){
					if(U[i-1][j]) U[i][j]=U[i-1][j];
					else U[i][j]=i;
				}
				else U[i][j]=0;
		for(int i=n;i>=1;i--)
			for(int j=m;j>=1;j--)
				if(b[i][j]){
					if(D[i+1][j]) D[i][j]=D[i+1][j];
					else D[i][j]=i;
				}
				else D[i][j]=0;
		
		for(int i=1;i<=n;i++){
			for(int j=1,las=1,x=-inf,y=inf;j<=m;j++){
				if(!b[i][j]){
					las=j+1;
					x=-inf,y=inf;
				}
				else{
					x=max(x,U[i][j]);
					y=min(y,D[i][j]);
					check(x,y,las,j);
				}
			}
			for(int j=m,las=m,x=-inf,y=inf;j>=1;j--){
				if(!b[i][j]){
					las=j-1;
					x=-inf,y=inf;
				}
				else{
					x=max(x,U[i][j]);
					y=min(y,D[i][j]);
					check(x,y,j,las);
				}
			}
		}
		if(ans==0) ans=-1;
		printf("%lld ",ans);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				U[i][j]=D[i][j]=b[i][j]=0;
	}
	puts("");
    return 0;
}



2024/12/15 16:19
加载中...