[ 백준 / C++ ] 1915 : 가장 큰 정사각형

[ 문제 ]

 

1915번: 가장 큰 정사각형

 

[ 접근방법 ]

 

현재 위치를 7시 방향 꼭짓점으로 하여 만들 수 있는 가장 큰 정사각형의 변의 길이를 dp table에 저장한다.

 

12시, 9시, 11시 방향의 값을 비교하여 현재 위치의 값을 갱신하면 된다.

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, dt[1010][1010], ans;
string s;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            int cnt;
            cnt = min(dt[i - 1][j - 1], min(dt[i - 1][j], dt[i][j - 1]));
            if (s[j - 1] == '1')
                dt[i][j] = cnt + 1;
            ans = max(ans, dt[i][j]);
        }
    }

    cout << ans * ans;

    return 0;
}