自动搬运

查看原文

来自洛谷，原作者为

	姬小路秋子 **

搬运于2025-08-24 21:45:18，当前版本为作者最后更新于2018-08-21 21:15:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道好（考智商）题。

看到求最大，我们不难想到用二分。如果你是这样想的话，那么恭喜你！

这样行不通。

我们不妨换种思路想（很难想到，对于我来说）。假设答案是k，那么读入数据（也就是最终矩阵）中必然有一个边长至少为k的全由同一种颜色组成的正方形，不然你最后一次进行标记时这个k*k的正方形应该在哪里。

然后我们把这个正方形中的所有点标记为任意颜色（即把它看做R，S通用）。为什么呢？这样做我们相当于撤销了当前的最后一次操作，而之前的操作又不确定这个位置标记的到底是哪种颜色。

当然，为了确保答案最优，这个正方形应该是最大的。

我们继续进行撤销操作（也就是逆推），然后继续求当前的最大正方形，直到没有点还有某种确定的颜色（意思是所有点都被标记了）。对于每一次求得的正方形边长取个min就是答案。

当然，最坏情况是每次找到的正方形边长都很小（甚至都为1），那么我们就要加个“可行性”剪枝了————在找了很多次正方形后带着当前得到的答案直接退出（事实证明你至少需要找不到2000一点的次数）

**PS：**一个点不能同时作为两个正方形的起始点（我用的是右下角）

上代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,sum,cnt,now,ans,l,r,f[101][101],g[101][101],mp[101][101],a[101][101];
char s[1010];
int main(){
	scanf("%d%d",&n,&m);
	ans=min(n,m);
	for(i=1;i<=n;i++){
		scanf("%s",s+1);
		for(j=1;j<=m;j++)
		 if(s[j]=='R')a[i][j]=1;
		  else a[i][j]=2;
	}
	now=n*m;
	while(now){
		sum=0;
		for(i=1;i<=n;i++)
		 for(j=1;j<=m;j++){
		 	f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
		 	g[i][j]=min(g[i-1][j],min(g[i][j-1],g[i-1][j-1]))+1;
		 	if(a[i][j]==1)g[i][j]=0;
		 	if(a[i][j]==2)f[i][j]=0;
		 	if(!mp[i][j]&&max(f[i][j],g[i][j])>sum){
		 		sum=max(f[i][j],g[i][j]);
		 		l=i;r=j;
		 	}
		 }
		mp[l][r]=1;
		ans=min(ans,sum);
		for(i=l-sum+1;i<=l;i++) 
		 for(j=r-sum+1;j<=r;j++){
		 	if(a[i][j])now--;
		 	a[i][j]=0;
		 }
		cnt++;
		if(cnt>5000)break; 
	}
	printf("%d",ans);
}