题目描述

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。

考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格

  1 2 3 4 5 6 7 8

1 . . . . . . . .

2 . # . . . # . .

3 . . . . . . . .

4 . . . . . . . .

5 . . . . . . . .

6 . . # . . . . .

7 . . . . . . . .

8 . . . . . . . .

最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。

输入

Line 1:	两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10，000）有树的方格的数量
Lines 2..T+1:	两个整数（1 <= 整数 <= N), 有树格子的横纵坐标

输出

输出文件只由一行组成，约翰的牛棚的最大边长。

样例输入

8 32 22 66 3

样例输出

5

f[i][j]表示以第i行第j列为右下角的牛棚的最大边长

注意取min并且要考虑f[i-1][j-1]才能满足限制条件 举个栗子推一推就好了

#include
    
     #include
     
      using namespace std;const int N=1000+5; int n,f[N][N],ans=0; bool a[N][N];int main(){	 int t,x,y;	scanf("%d%d",&n,&t); 	 while(t--)	  {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-1],min(f[i-1][j],f[i][j-1]))+1;     ans=max(ans,f[i][j]);    } printf("%d",ans);   return 0;}