1051번: 숫자 정사각형
N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는
www.acmicpc.net
1. 풀이방법.
- 모든 정사각형의 4개의 꼭지점이 같은지 확인해주시면 됩니다.
- 입력이 붙어있길래 전 char 배열을 선언해서 입력을 받았습니다.
- 숫자가 들어오지만 , 계산하는 과정은 없고 같은지만 확인하면 되므로 따로 숫자로 변환시키지는 않았습니다.
2. 주의사항
- 하나짜리도 정사각형 입니다. (어찌보면 당연)
- 전그냥 따로 예외로 빼주었습니다.
3. 나의코드
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int N, M;
char nemo[51][51]; //0~ n-1, 0 ~ m-1
int maxcnt = 0;
void inputs() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> nemo[i][j];
}
}
}
int samenemo(int x, int y, int c) {
if (nemo[x][y] == nemo[x + c][y] && nemo[x][y] == nemo[x][y + c]
&& nemo[x][y] == nemo[x + c][y + c]) return true;
else return false;
}
void makecase(int cnt)
{
for (int i = 0; i < N-cnt; i++) {
for (int j = 0; j < M-cnt; j++) {
if (samenemo(i, j,cnt)) {
if (maxcnt < cnt) {
maxcnt = cnt;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
if (N == 1 || M == 1) { cout << 1 << "\n"; return 0; }
for (int i = 1; i < min(N, M); i++) {
makecase(i); // 시작 index와 한 변의 길이
}
cout << (maxcnt+1)*(maxcnt+1) << "\n";
return 0;
}