가장 큰 정사각형

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

1915번: 가장 큰 정사각형

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
 
using namespace std;
 
int arr[1004][1004];
int dp[1004][1004];
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    long ans = 0;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // 한 자리 수를 붙여서 받으므로
            scanf("%1d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (i == 0 || j == 0)
            {
                if (arr[i][j] == 1)
                {
                    dp[i][j] = 1;
                    if (dp[i][j] > ans)
                        ans = dp[i][j];
                }
                else
                    dp[i][j] = 0;
 
                continue;
            }
 
            if (arr[i][j] == 1)
            {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (dp[i][j] > ans)
                    ans = dp[i][j];
            }
        }
    }
 
    cout << ans * ans << '\n';
 
    return 0;
}