BOJ-1937欲張りパンダ

1937号欲張りパンダ
パンダは今いる竹を食べ終わって、上下左右に移動します.このとき、移動する場所の竹が今いる場所の竹より少ないと、移動せずに餓死することになります.
上記の場合、パンダが初めてどこかに位置したとき、問題はパンダが最も長く生きられる時間を探すことです.
トラブルシューティングポリシー
たとえば,パンダが(1,1)->(1,2)->(2,2)に移動するとする.
(1,1)出発時の生存時間は3日間であった.
また,(1,2)出発時の生存期間は2日間であった.
以前に選択した座標の移動パスに現在選択されている座標がある場合、現在選択されている座標は、個別に計算する必要がなく、以前の座標の日数よりも無条件に小さくなります.
また、新しく選択した座標から移動経路の他の座標から出発したときに通過する箇所をもう一度通過すると、その時点で保存した値と現在累積した値とを比較することでより大きな値が保存されます.
すなわち、DPに記憶された値を利用する.
問題の解決手順は次のとおりです.

竹の量は降順に並ぶ.

竹は多いから少ないまで.

移動中に移動位置に格納された期間を現在の期間+1と比較し、より大きな値を保存します.

記憶値の中で最大の値を求める.

コード#コード#

 #include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int arr[501][501];
int visited[501][501];
int xpo[4] = {-1,1,0,0};
int ypo[4] = {0,0,-1,1};
vector<pair<int, pair<int,int>>> v;
int n;
int dp(){
    for(int i=0;i<v.size();i++)
    {
        int x = v[i].second.first;
        int y = v[i].second.second;

        for(int j=0;j<4;j++)
        {
            int nx = x + xpo[j];
            int ny = y + ypo[j];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;

            if(arr[nx][ny] > arr[x][y])
            {
                if(visited[x][y] < visited[nx][ny] + 1)
                    visited[x][y] = visited[nx][ny] + 1;
            }
        }
        if(visited[x][y] == 0)
            visited[x][y] = 1;
    }

    int max = 0;
    for(int k=0;k<n;k++)
    {
        for(int j=0;j<n;j++)
        {
            if(visited[k][j] > max)
                max = visited[k][j];
        }
    }
    return max;
}
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++)
        {
            cin >> arr[i][j];
            v.push_back(make_pair(-arr[i][j], make_pair(i,j)));
        }
    }

    sort(v.begin(), v.end());

    cout << dp();

    return 0;
}

ソース:https://www.acmicpc.net/problem/1937