题目传送门
(f_{i,j})表示以((i,j))为左下角能得到的最大正方形的边长.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,t,f[1001][1001],ans;
bool a[1001][1001];
inline int min(int s,int d) {
if(s > d) return d;
return s;
}
inline int max(int s,int d) {
if(s < d) return d;
return s;
}
int main() {
scanf("%d%d",&n,&t);
for(int i = 1;i <= t; i++) {
int x,y;
scanf("%d%d",&x,&y);
a[x][y] = 1;
}
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
if(!a[i][j])
f[i][j] = min(f[i-1][j],min(f[i][j-1],f[i-1][j-1])) + 1,ans = max(ans,f[i][j]);
printf("%d",ans);
return 0;
}