문제
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
4 4 0100 0111 1110 0010
예제 출력 1
4
내 소스
#include <iostream>
using namespace std;
int main(){
int n;
int m;
int i;
int j;
int min;
int answer = 0;
int **arr;
int **dp;
char c;
cin >> n;
cin >> m;
arr = new int*[n];
dp = new int*[n];
for(i=0; i<n; i++){
dp[i] = new int[m];
arr[i] = new int[m];
for(j=0; j<m; j++){
cin >> c;
arr[i][j] = c - '0';
dp[i][j] = 0;
}
}
for(j=0; j<m; j++){
dp[0][j] = arr[0][j];
}
for(i=0; i<n; i++){
dp[i][0] = arr[i][0];
}
for(i=1; i<n; i++){
for(j=1; j<m; j++){
if(arr[i][j]==1){
min = dp[i-1][j-1];
if(dp[i-1][j] < min){
min = dp[i-1][j];
}
if(dp[i][j-1] < min){
min = dp[i][j-1];
}
dp[i][j] = min + 1;
}
}
}
for(i=0; i<n; i++){
for(j=0; j<m; j++){
if(dp[i][j] > answer){
answer = dp[i][j];
}
}
}
cout << answer * answer;
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준/DP] 2294 - 동전 2 (0) | 2020.02.01 |
---|---|
[백준/DP] 14501 - 퇴사 (0) | 2020.01.26 |
[백준/DP] 1912 - 연속합 (0) | 2020.01.21 |
[백준/구현] 2490 - 윷놀이 (0) | 2019.10.13 |
[백준/DFS] 1890 - 점프 (0) | 2019.10.13 |