백준 1051번: 숫자 정사각형 (C++)

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

1051번: 숫자 정사각형

---

Level: Silver IV

Solved By: Implementation

 

모서리의 값이 전부 같은 정사각형 중 제일 큰 넓이를 구하는 것이 문제입니다.

그래서 사각형의 모서리 값을 구하는 함수(getMax)를 짜는 것이 이번 문제의 중요 포인트입니다.

pair형을 리턴하는 것은 아무 상관 없으니 참고바랍니다.

#include <iostream>
#define MAX 51
using namespace std;

int N, M;
int board[MAX][MAX];

pair<int, int> getMax(int len){
    int ret = -1;
    for(int i = 1; i + len - 1 <= N; i++){
        for(int j = 1; j + len - 1 <= M; j++){
            int lu = board[i][j], ru = board[i][j + len - 1];
            int ld = board[i + len - 1][j], rd = board[i + len - 1][j + len - 1];
            
            if(lu == ru && ld == rd && lu == ld){
                ret = max(ret, lu);
            }
        }
    }
    return {len, ret};
}

int main(){
    cin >> N >> M;
    int max_length = min(N, M);
    
    for(int i = 1; i <= N; i++){
        string a; cin >> a;
        for(int j = 0; j < M ; j++){
            board[i][j + 1] = a[j] - '0';
        }
    }
    
    int res = 0;
    
    for(int i = 1; i <= max_length; i++){
        auto q = getMax(i);
        if(q.second == -1) continue;
        res = max(res, q.first * q.first);
    }
    
    cout << res;
}