正题

题目链接:https://www.luogu.org/problemnew/show/P3100

---

题目大意

一个空矩阵，每次可以将$B\ast B$的矩阵覆盖为$R$或者$B$。

求$B$最大是多少使得可以覆盖使得原矩阵成为目标矩阵。

---

解题思路

我们考虑贪心，先分析一下性质。

假设答案为$k$，那么目标矩阵上必然有一个边长为$k$的同颜色正方形。当然考虑最优，我们会让$k$越大越好。

我们可以每次寻找一个同颜色的最大正方形，然后每次将这个正方形全都覆盖为两种颜色通用，直到所有的都被覆盖，每次取这个最大正方形的最小边长。

这时就有问题了，我们如何用$dp$计算时保证这个正方形内必定有没有被覆盖的情况呢$?$其实我们可以用一个$v_{i,j}$表示以$v$为右下角的最大矩阵是否覆盖，这样我们保证每次都找没有覆盖的情况就好了。

但是这是我们发现单单这样会$TLE$，那我们只有限制一下运行次数就可以了，因为若到后面，基本发现不了更小的正方形。

---

$code$

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,f[110][110],x,y,ans,sum;
int a[110][110],k,g[110][110];
bool v[110][110];
void get_ans()
{sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;g[i][j]=min(g[i-1][j-1],min(g[i-1][j],g[i][j-1]))+1;if(a[i][j]==0) f[i][j]=0;if(a[i][j]==1) g[i][j]=0;if(v[i][j]||max(f[i][j],g[i][j])<=sum) continue;sum=max(f[i][j],g[i][j]);x=i;y=j;}v[x][y]=1;ans=min(ans,sum);for(int i=0;i<sum;i++)for(int j=0;j<sum;j++){if(a[x-i][y-j]!=3) k--;a[x-i][y-j]=3;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char x;cin>>x;a[i][j]=(x=='R');}k=n*m;ans=n;for(int i=1;i<=5000&&k;i++) get_ans();printf("%d",ans);
}