洛谷 P1387 最大正方形（DP）

题意：给一个n*m的01矩阵，求最大的全为1的正方形的边长，n,m <= 100

数据范围比较小可以有多种做法，这里用DP

设dp[i][j]为（i，j）为右下角的最大正方形边长，显然只有1能做正方形的右下角

如果某个dp[i][j] != 0 就说明（i，j）向上、向左的dp[i][j]格都是1

对于一个点，画出它左上、左边、上面三个点相应的最大正方形

 

 

emmmm图比较草率就意会一下吧。。。可以看出是最小的正方形边长+1

所以dp[i][j] = min{ dp[i-1][j-1], dp[i][j-1], dp[i-1][j] } + 1

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define LL long long
#define debug(x) cout << "[" << x << "]" << endl
using namespace std;

const int mx = 110;
int dp[mx][mx];

int main(){
    int n, m, ans = 0, a;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a);
            if (a == 1) dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
            ans = max(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}