백준 1937 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

dp[x][y] 를 (x, y)의 좌표에서의 최대 이동횟수라 했을 때

dp[x][y] = 1 + max(dp[x - 1][y], dp[x + 1][y], dp[x][y-1], dp[x][y+1] )        // 1+ max(상하좌우)

라고 할 수 있다,

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int N;
int trees[500][500];
int dp[500][500];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int dfs(int x, int y)
{
    if (dp[x][y] != -1)
        return dp[x][y];
    dp[x][y] = 0;
    bool flag = false;
    int m = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < N && 0 <= ny && ny < N)
        {
            if (trees[x][y] < trees[nx][ny])
            {
                flag = true;
                m = max(m, dfs(nx, ny));
            }
        }
    }
    
    if (flag)
        dp[x][y] = 1 + m;
    return dp[x][y];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int m;
            cin >> m;
            trees[i][j] = m;
        }
    }

    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int cnt = dfs(i, j);
            ans = max(ans, cnt);
        }
    }
    cout << ans + 1;
}