백준 1915번 가장 큰 정사각형

문제 링크입니다: https://www.acmicpc.net/problem/1915

(←, ↖, ↑의 인덱스 값 중 최소) + 1이 (i, j)에서 만들 수 있는 가장 큰 정사각형 변의 길이라는 것을 알아내는 것이 핵심이였던 문제였습니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 1000;

 

int N, M;

string arr[MAX];

int cache[MAX][MAX];

 

int getArea(void)

{

        int side = 0; //변의 최대 길이

        for (int i = 0; i < N; i++)

               for (int j = 0; j < M; j++)

               {

                       //세 방향 확인할 수 없는 경우

                       if (i == 0 || j == 0)

                              cache[i][j] = arr[i][j] - '0';

                       else if (arr[i][j] == '1')

                              //←, ↖, ↑ 방향을 확인 후 최소 값 + 1

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

                       side = max(side, cache[i][j]);

               }

        return side * side;

}

 

int main(void)

{

        cin >> N >> M;

        if (N<1 || N>MAX || M<1 || M>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               cin >> arr[i];

 

        cout << getArea() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~