[백준] [c++] 1915 번 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

1915번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 가장 큰 정사각형 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 14697 4368 3130 28.813% 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.  입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어...

www.acmicpc.net

가장 큰 정사각형 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	14697	4368	3130	28.813%

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

​

​

​

​

현 위치가 1인데, 왼쪽, 왼쪽대각선, 위쪽 위치가 0보다 크다면? (처음엔 1) 현재 위치가 정사각형이 될 수 있으므로 1을 더해준다. 그러다가 예를들어 왼,대,위가 2,2,2면 현재위치가 3이되고 만약 그다음에 나올 수 있는 정사각형이 없다면 3이 최대가 됨.

그러나 왼,대,위 중 제일 작은값에 1을 더해줘야됨. 하나라도 정사각형을 못만든다면 제일 크게 못만들기 때문.

글고 전부 0일때와 전부 1일때 예외 처리 해줘야됨.

​

01000

01110

01110

01111

10001

​

01000

01100

01110

01111

10001

​

000

000

000

​

111

111

111

​

테스트케이스 이걸로 해보면서 풀었음. freopen("1.txt", "r", stdin); txt 저장해놓고 테스트하는게 좋을듯.

 

#include <iostream>
#include <algorithm>
using namespace std;
int rect[1001][1001];
int main() {

	int n, m;
	scanf("%d %d", &n, &m);
	int mx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &rect[i][j]);
			if (rect[i][j]) {
				mx = 1;
			}
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (rect[i][j]>0&&rect[i - 1][j]>0&&rect[i][j - 1]>0&&rect[i - 1][j - 1]>0) {
				rect[i][j] = min(rect[i - 1][j],min( rect[i][j - 1], rect[i - 1][j - 1]))+1;
				mx = max(mx, rect[i][j]);
			}
		}
	}
	cout << mx*mx;
}