4095번: 최대 정사각형

https://www.acmicpc.net/problem/4095


$O(tnm)$

dp[i][j]:(i,j)로 끝나는 최대 정사각형의 한 변 길이
dp[i][j]=
(i,j)가 1이면 min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
0이면 0

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, dp[1001][1001], r;
int main() {
    while (scanf("%d%d", &n, &m), n) {
        r = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1, x; j <= m; j++) {
                scanf("%d", &x);
                dp[i][j] = (min({ dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] }) + 1)*x;
                r = max(r, dp[i][j]);
            }
        }
        printf("%d\n", r);
    }
    return 0;
}