动态规划。前面的章节中还有一个与这个基本上一样的题。

• 状态 o F[i][j] 表示以(i,j)为左上角最大正方形的边长

• 初始条件 o 如果(i,N)没有障碍 F[i][N]=1 否则 F[i][N]=0 o 如果(N,i)没有障碍 F[N][i]=1 否则 F[N][i]=0

• 状态转移方程 o F[i][j]=min(F[i+1][j],F[i][j+1],F[i+1][j+1])+1;

  USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
    TASK: bigbrn
    LANG: C++
  
    Compiling...
    Compile: OK
  
    Executing...
       Test 1: TEST OK [0.011 secs, 6752 KB]
       Test 2: TEST OK [0.000 secs, 6752 KB]
       Test 3: TEST OK [0.000 secs, 6756 KB]
       Test 4: TEST OK [0.000 secs, 6756 KB]
       Test 5: TEST OK [0.000 secs, 6756 KB]
       Test 6: TEST OK [0.000 secs, 6752 KB]
       Test 7: TEST OK [0.000 secs, 6752 KB]
       Test 8: TEST OK [0.011 secs, 6756 KB]
       Test 9: TEST OK [0.011 secs, 6756 KB]
       Test 10: TEST OK [0.032 secs, 6752 KB]
       Test 11: TEST OK [0.032 secs, 6752 KB]
       Test 12: TEST OK [0.032 secs, 6756 KB]
       Test 13: TEST OK [0.022 secs, 6756 KB]
       Test 14: TEST OK [0.022 secs, 6752 KB]
       Test 15: TEST OK [0.043 secs, 6752 KB]
  
    All tests OK.
    
    Your program ('bigbrn') produced all correct answers!  This is your
    submission #3 for this problem.  Congratulations!
    
    

/*
ID: cmykrgb1
PROG: bigbrn
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXN 1001

using namespace std;

ifstream fi("bigbrn.in");
ofstream fo("bigbrn.out");

int M[MAXN][MAXN],N,ans;

void init()
{
    int T,x,y,i;
    fi >> N >> T;
    for (i=1;i<=T;i++)
    {
        fi >> x >> y;
        M[x][y]=-1;
    }
}

inline int min(int a,int b,int c)
{
    if (a<=b && a<=c) return a;
    if (b<=a && b<=c) return b;
    return c;
}

void dynamic()
{
    int i,j;
    for (i=1;i<=N;i++)
    {
        if (M[N][i]==0)    M[N][i]=1;
        else            M[N][i]=0;
        if (M[i][N]==0)    M[i][N]=1;
        else            M[i][N]=0;
    }
    for (i=N-1;i>=1;i--)
        for (j=N-1;j>=1;j--)
            if (M[i][j]==-1)
                M[i][j]=0;
            else
            {
                M[i][j]=min(M[i+1][j],M[i][j+1],M[i+1][j+1])+1;
                if (M[i][j]>ans)
                    ans=M[i][j];
            }
}

void print()
{
    fo << ans << endl;
    fi.close();
    fo.close();
}

int main()
{
    int i,j;
    init();
    dynamic();
    print();
    return 0;
}