[1051번] 숫자 정사각형

문제 출처 :https://www.acmicpc.net/problem/1051

알고리즘 분석 :

문제 해결에 필요한 사항

1. 부르트 포스

이 문제는 최대 최대 길이, 최대 가로, 최대 세로를 모두 해도 50*50*50이기에 O(n^3)이어도 해결 할 수 있다.

idx는 변의 길이를 의미하고, i는 행, j는 열을 의미한다.

네 꼭지점이 같은지만 확인하면 쉽게 풀 수 있는 문제이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include <iostream> #include <cstdio> #include <memory.h>   #define max(a,b)(a > b ? a : b)   using namespace std;   int arr[200][200]; int main() {     int n, m;     scanf("%d %d", &n, &m);       memset(arr, -1, sizeof(arr));     for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             scanf("%1d", &arr[i][j]);       int ans = 0;     // 크기     int x = 1;     for (int idx = 0; idx <= 50; idx++)     {                 bool chk = false;         for (int i = 0; i < n; i++)         {             for (int j = 0; j < m; j++)                 if (arr[i][j] == arr[i][j + x] && arr[i][j + x] == arr[i + x][j] && arr[i][j] == arr[i + x][j + x])                 {                     ans = max(ans, x);                     chk = true;                     break;                 }             if (chk)                 break;         }         x++;     }       ans++;     printf("%d", ans * ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus