vijos 1057 盖房子 简单DP

描述

永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。

但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。

他希望找到一块最大的正方形无瑕疵土地来盖房子。

不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。

现在，您也来试试吧。

格式

输入格式

输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。

输出格式

一个整数，最大正方形的边长。

样例1

样例输入1

样例输出1

限制

各点时限均为1s。

题意：找一个最大的正方形。

思路：很简单的一个思路，从左，上，左上方向转移即可，状态设计为地图为i X j时的最大正方形边长。

/** @Date    : 2016-12-13-19.39

  * @Author  : Lweleth ([email protected])

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int dp[1010][1010];

int main()

{

    int n, m;

    cin >> n >> m;

    MMF(dp);

    for(int i = 1; i <= n; i++)

    {

        for(int j = 1; j <= m; j++)

        {

            scanf("%d", &dp[i][j]);

        }

    }

    int ma = 0;

    for(int i = 1; i <= n; i++)

    {

        for(int j = 1; j <= m; j++)

        {

            if(dp[i][j] != 0)

            {

                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;

            }

            ma = max(dp[i][j], ma);

        }

    }

    printf("%d\n", ma);

    return 0;

}