[greedy method] 스노보드/snowboard

프로그램 명: snowboard

제한시간: 1 초

마이클은 스노우보드를 매우 즐기는 녀석이다. 그런데 , 스노우 보드 탈 때 한가지 문제점은 내려갈때는 신나지만 올라갈때는 다시 걸어서 올라가거나 리프트를 타야하는 점이다. 마이클은 다시 올라가는 것을 되도록이면 피하고 싶어한다. 우리가 마이클을 도와주도록 하자.

다음은 입력의 한 예이다.

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

각각의 숫자는 산의 각 지점의 높이다. 스노우보드 움직일 때는 항상 높은 지점에서 낮은 지점으로만 움직여야 한다. 내려오는 코스는 산의 모든 지점을 포함하지 않을 수 있다. 위의 데이터에서 최적해는 25-24-..-2-1 이다.

입력 방법

첫째 줄에는 코스의 세로길이 R 와 가로길이 C 가 주어진다.(단, R 과 C 는 100 이하의 양의 정수). 각 지점의 높이는 100 을 넘지않은 정수로 주어진다.

출력 방법

주어진 데이터에서 가장 긴 코스의 길이를 출력한다.

입출력의 예

입력

10 5

56	14	51	58	88
26	94	24	39	41
24	16	8	51	51
76	72	77	43	10
38	50	59	84	81
5	23	37	71	77
96	10	93	53	82
94	15	96	69	9
74	0	62	38	96
37	54	55	82	38

출력

7

*참고*

출처: http://acm.uva.es/p/v102/10285.html

 

#include <stdio.h>
 
#define MAX 105
 
int R, C;
int Map[MAX][MAX];
int Visit[MAX][MAX];
 
int MaxCount=0;
 
void input()
{
    int i, j;
    scanf("%d", &R);
    scanf("%d", &C);
    for(i=1; i<=R; i++)
    {
        for(j=1; j<=C; j++)
        {
            scanf("%d", &Map[i][j]);        
            Map[i][j]++;
        }
    }
}
 
void dfs(int x, int y, int depth)
{
    int i;
    int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
    if(depth > MaxCount)
        MaxCount = depth;
 
    for(i=0; i<4; i++)
    {
        if(Visit[y+dir[i][1]][x+dir[i][0]] == 0)
        {
            if(Map[y][x] > Map[y+dir[i][1]][x+dir[i][0]] 
                && Map[y+dir[i][1]][x+dir[i][0]] > 0)
            {
                Visit[y+dir[i][1]][x+dir[i][0]]=1;
                dfs(x+dir[i][0], y+dir[i][1], depth+1);
                Visit[y+dir[i][1]][x+dir[i][0]]=0;
            }
        }
    }
}
 
void process()
{
    int i, j;
 
    for(i=1; i<=R; i++)
    {
        for(j=1; j<=C; j++)
        {
            dfs(j, i, 0);
        }
    }
}
 
int main(void)
{
    input();
    process();
    printf("%d\n", MaxCount+1);
 
    return 0;
}