[알고리즘 문제] 백준1051 - 숫자 정사각형

www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

완전탐색 문제입니다. 변의 길이가 1,2,3...일때 구할 수 있는 정사각형을 모두 구하고 꼭지점을 검사하였습니다. 길이가 1인 정사각형도 존재하기 때문에 ans=1부터 시작해야 합니다. 

 

#include <iostream>
#include <algorithm>

using namespace std;

bool check(int yPoint, int xPoint, int length, int arr[51][51]) // 각 꼭지점의 값이 모두 동이한지 검사
{
    return arr[yPoint - length][xPoint - length] == arr[yPoint][xPoint - length] && arr[yPoint - length][xPoint - length] == arr[yPoint - length][xPoint] && arr[yPoint - length][xPoint - length] == arr[yPoint][xPoint];
}

int main()
{

    int height, width;
    int ans = 1;
    int arr[51][51];

    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        string s;
        cin >> s;
        for (int x = 0; x < s.length(); x++)
        {
            arr[y][x] = s[x] - '0';
        }
    }

    int maxLen = height > width ? width : height;

    for (int length = 1; length < maxLen; length++) // length는 꼭지점 간의 간격
    {
        for (int y = 0; y < height - length; y++) 
        {
            int yPoint = length + y;
            for (int x = 0; x < width - length; x++)
            {
                int xPoint = length + x;

                if (check(yPoint, xPoint, length, arr))
                {
                    ans = max(ans, ((length + 1) * (length + 1)));
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}