Vijos 1057 盖房子

二次联通门 : Vijos 1057 盖房子

/*
    Vijos 1057 盖房子
    
    简单的dp
    
    当前点(i, j)所能构成的最大的正方形的边长
    为点(i - 1, j - 1)与(i, j - 1), (i - 1, j)三点中最小的边长构成..
    一遍递推, 一边取最大即可 
*/
#include <cstdio>

#define Max 1009

inline int min (int a, int b)
{
    return a < b ? a : b;
}

inline int max (int a, int b)
{
    return a > b ? a : b;
}

void read (int &now)
{
    now = 0;
    register char word = getchar ();
    while (word < '0' || word > '9')
        word = getchar ();
    while (word >= '0' && word <= '9')
    {
        now = now * 10 + word - '0';
        word = getchar ();
    }
}

int N, M;
int map[Max][Max];

int main (int argc, char *argv[])
{
    read (N);
    read (M);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            read (map[i][j]);
    int Answer = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (map[i][j])
            {
                map[i][j] += min (map[i - 1][j - 1], min (map[i - 1][j], map[i][j - 1]));
                Answer = max (Answer, map[i][j]);
            }
    printf ("%d", Answer);
    return 0;
}