[백준 1937] 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

1/8일 풀었던 문제

요구사항

1. 판다가 제일 오래 살 수있는 경로 구하기

 

풀이

1. dp로 현재 좌표에서 부터 몇일을 살 수 있는지 미리 저장한다.

 

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
int n;
int map[501][501];
int dp[501][501];
int dr[4] ={-1,0,1,0};
int dc[4] ={0,-1,0,1};
int f(int r, int c){
    int &ret=dp[r][c];
    if(ret !=1){
        return ret;
    }
    for(int i=0 ; i < 4; i++){
        int nr = r+dr[i];
        int nc = c+dc[i];
        if(nr<0 || nc<0 || nr>=n || nc>=n)
            continue;
        if(map[nr][nc]>map[r][c]){
            ret = max(ret,f(nr,nc)+1);
        }   
    }
    return ret;
}
int main(){
    cin>>n;
    for(int i=0 ; i < n ; i++){
        for(int j=0 ; j <n ; j++){
            dp[i][j]=1;
            scanf("%d",&map[i][j]);
        }
    }
    int ans=0;
    for(int i=0 ; i < n ; i++){
        for(int j=0 ; j <n ; j++){
            ans=max(ans,f(i,j));
        }
    }
    cout<<ans<<endl;
}