求助!!!
查看原帖
求助!!!
114154
陆朱良雨楼主2020/10/16 18:52
#include<bits/stdc++.h>
using namespace std;
//随机化二分
#define N 1001
int n,m,sum[N][N],f[N];
char c;
bool check(int x,int y){
	for(int i=n-x+1;i<=n;i++)
	 for(int j=m-y+1;j<=m;j++)
	  if(sum[i][j]+sum[i-x][j-y]-sum[i][j-y]-sum[i-x][j]==x*y) return true;
	  return false;
}
int ran(int x,int y){
	return rand()%(y-x+1)+x;
}
int main(){
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++){
	 	cin>>c;
	 	sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	 	if(c=='F') sum[i][j]++;
	 }
	 int ln=0,lm=0,rn=n,rm=m;
	 while(ln!=rn&&lm!=rm){
	 	int midn=ran(ln,rn),midm=ran(lm,rm);
	 	if(check(midn,midm))  	{ln=midn;lm=midm;}
	 	else  {rn=midn;rm=midm;}
	 }
	 cout<<3*ln*lm<<endl;
	return 0;
}
2020/10/16 18:52
加载中...