[C++]白俊1520:下り坂

💻 問題解決のプロセス
1.DFSの使用
「M*N」形のテーブルは、上下左右に移動できるとグラフが出てきます.また,経路は価格が徐々に小さくなる降順に並べるべきである.
DFSを使用する場合は、東、西、南、北の4つの位置で回転し、次の位置の値が現在の値より小さい場合はその位置に移動します.
2.しかしDFSの実行時間は負担になります.
DFSを使用する場合は、再帰+アクセス済みのパスを再呼び出しできます.
>アクセスした場所に再アクセスする場合は、以前にアクセスした結果値を使用します.
だからDPを使います.
私たちは今の位置で4つの場所を探さなければなりません.
例に従って東->西->南->北の順に探索すれば?
東探索が終わった後、次の方向である西探索では、東探索時に訪れた位置を再訪問した.
このロケーションがi,jである場合、4つのすべてのロケーションにアクセスする必要はなく、値をdp[i][j]とします.dp[i][j]=i,j位置から到達点までの到達可能経路数
3.特定位置のDP値は「0」であってもよいことに注意してください.
東、西、南、北のすべての現在値がインデックス範囲より小さいか、または超えている場合、その位置のDP値は「0」になります.
初期時、DPの初期化値は0である.

if( dp[i][j] != 0 ){
	return dp[i][j]
}

このようにdp値があるかどうかを決定すると、タイムアウトが発生します.
dp値は0である可能性があるため、0よりも-1の方が良い可能性がある.
💻 コードの作成

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int MAX_SCOPE = 501; 
const int DIRECTION_CASE = 4;
int M,N;
int height[MAX_SCOPE][MAX_SCOPE];
int dp[MAX_SCOPE][MAX_SCOPE];
bool visited[MAX_SCOPE][MAX_SCOPE] = {0,};

// 동,남,서,북 순서
int direction_m[DIRECTION_CASE] = { 0, 1, 0, -1 };
int direction_n[DIRECTION_CASE] = { 1, 0, -1, 0 };

bool IsPossiblePosition(int a, int b)
{
    return ( 0<a && a<=M ) && ( 0<b && b<=N ) && visited[a][b]==false;
}

int CountPathFromIndexAt(int a, int b)
{
    if( dp[a][b]!=-1 ){
        return dp[a][b];
    }
    if( a==M && b==N ){
        return 1;
    }

    visited[a][b] = true;
    int cnt = 0;

    for (int i = 0; i < DIRECTION_CASE; i++)
    {
        int next_a = direction_m[i] + a;
        int next_b = direction_n[i] + b;
        if( IsPossiblePosition(next_a,next_b) && height[next_a][next_b] < height[a][b] ){
            cnt += CountPathFromIndexAt(next_a,next_b);
        }
    }
    dp[a][b] = cnt;
    visited[a][b] = false;
    return dp[a][b];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> M >> N;
    for (int i = 1; i <= M; i++){
        for (int j = 1; j <= N; j++){
            cin >> height[i][j];
            dp[i][j] = -1;
        }
        cin.ignore();
    }
    
    cout << CountPathFromIndexAt(1,1);
}
    

リンク
https://www.acmicpc.net/problem/1520