首先，本题是一道最大子矩阵问题，且m，n较小，可以使用DP做，
与 洛谷 [P1387]最大正方形 做法相同。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN=5005;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
bool ff[MAXN][MAXN];
int dp[MAXN][MAXN],n,t,ans;
int main(){
freopen("in.txt","r",stdin);
n=init();t=init();
for(int i=1;i<=t;i++){
int x=init(),y=init();
ff[y][x]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ff[i][j]) dp[i][j]=0;
else{
dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
ans=max(dp[i][j],ans);
}
}
}
cout<<ans;
fclose(stdin);
return 0;
}
本题也可以使用悬线法求最大子矩阵，首先 O(n^2) 预处理，对于矩阵上的每一个点，我们可以：
1.从它向上引一条悬线，遇到边界或障碍点停止，h[i][j] 数组记录从点 (i,j) 向上的悬线长度。
2.向左延伸，遇到边界或障碍点停止，l[i][j] 数组记录从点 (i,j) 向左最大能延伸的长度。
3.向右延伸，遇到边界或障碍点停止，r[i][j] 数组记录从点 (i,j) 向右最大能延伸的长度。
但是这样是不够的， 因为，L[i][j] 和 L[i][j] 的值都各自取决于 L[i-1][j] 和 R[i-1][j]。（因为为保证成为一个矩形，L[i][j] 不能超过 L[i-1][j]，R同理）
所以枚举点对 l 和 r 进行更新，对 L[i-1][j] 与 l[i][j] 取 min，r 同理。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN=1005;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
int n,t,l[MAXN][MAXN],r[MAXN][MAXN],L[MAXN][MAXN],R[MAXN][MAXN],H[MAXN][MAXN],ans;
bool ff[MAXN][MAXN];
int main(){
freopen("in.txt","r",stdin);
n=init();t=init();
for(int i=1;i<=t;i++){
int x=init(),y=init();
ff[x][y]=1;
}
for(int i=1;i<=n;i++){
l[i][1]=0;
for(int j=2;j<=n;j++){
if(ff[i][j]){
l[i][j]=j;
}else l[i][j]=l[i][j-1];
}
r[i][n]=n+1;
for(int j=n-1;j>=1;j--){
if(ff[i][j]){
r[i][j]=j;
}else r[i][j]=r[i][j+1];
}
}
for(int j=1;j<=n;j++){
H[1][j]=1;L[1][j]=l[1][j];R[1][j]=r[1][j];
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++){
if(ff[i-1][j]){
H[i][j]=1;
L[i][j]=l[i][j],R[i][j]=r[i][j];
}else{
H[i][j]=H[i-1][j]+1;
L[i][j]=max(L[i-1][j],l[i][j]);
R[i][j]=min(R[i-1][j],r[i][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int len=min(H[i][j],R[i][j]-L[i][j]-1);
//if(len==6) printf("%d %d
",i,j);
ans=max(ans,len);
}
}
cout<<ans;
fclose(stdin);
return 0;
}