알고리즘/Backjoon
[C++] 14925 - 목장 건설하기
ShinDongJun
2020. 1. 17. 03:06
문제 링크 : https://www.acmicpc.net/problem/14925
14925번: 목장 건설하기
랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미
www.acmicpc.net
|
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
49
50
51
|
#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int M, N;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int i, j;
int cnt = 0;
cin >> M >> N;
for(i = 0; i < M; ++i){
for(j = 0; j < N; ++j){
cin >> dp[i][j];
if(dp[i][j] != 0)
dp[i][j] = -1;
}
}
for(i = 0; i < M; ++i){
for(j = 0; j < N; ++j){
if(dp[i][j] != -1)
{
if(i == 0 || j == 0)
dp[i][j] = 1;
else if(i > 0 && j > 0)
{
int k = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));
if(k == -1)
dp[i][j] = 1;
else
dp[i][j] += k + 1;
}
if(cnt < dp[i][j])
cnt = dp[i][j];
}
}
}
cout << cnt << endl;
return 0;
}
|