SDJ( 수돈재 아님 ㅎ )

[C++] 14925 - 목장 건설하기 본문

알고리즘/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;
}
저작자표시

'알고리즘 > Backjoon' 카테고리의 다른 글

[C++] Mini Sudoku X  (0) 2020.01.20
[C++] 15918 - 랭퍼든 수열쟁이야!!  (0) 2020.01.20
[C++] 2981 - 검문  (0) 2020.01.16
[C++] 17836 - 공주님을 구해라!  (0) 2020.01.15
[C++] 2780 - 비밀번호  (0) 2020.01.15
'알고리즘/Backjoon' Related Articles more
Comments