[白俊]1520番下り坂

1833 ワード
白駿 テキストリンク

[白俊]1520番下り坂


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

質問する



にゅうしゅつりょく



質問へのアクセス


これはdp問題です.
これは単純な問題だ.これはdfsとdpを混合する問題である.edgeは現在、自身の高さより小さいノードのみで接続されており、一方向図である.
現在の位置から宛先に到達できる経路が何本あるかを計算し、nodeに転送し、以前のnodeが自分に接続されたノードから宛先に到達できる数を求める.

コード実装（C++）

#include <iostream>
#include <cstring>

using namespace std;

int map[501][501];
int cache[501][501];
int M, N;
int xMove[4] = {0,0,1,-1};
int yMove[4] = {-1,1,0,0};
int dp(int i, int j){
    if(i == M - 1 && j == N - 1) return 1;
    int& res = cache[i][j];
    if(res != -1) return res;
    res = 0;
    for(int k = 0 ; k < 4 ; k++){
        int nextI = i + yMove[k]; int nextJ = j + xMove[k];
        if(nextI < 0 || nextJ < 0 || nextI >= M || nextJ >= N ) continue;
        if(map[i][j] <= map[nextI][nextJ]) continue;
        res += dp(nextI, nextJ);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> M >> N;
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> map[i][j];
        }
    }
    memset(cache, -1, sizeof(cache));
    cout << dp(0,0) << "\n";
}
[Spring Batch] Batch Job
JS 100第12題ゲームキャラクタークラスの作成