リンク

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

質問する

N×Nゲームボードに数字が書いてあります.このゲームの目標は、一番左上から一番右下にジャンプし、ルールに従って行うことです.
各セルの数値は、現在のセルから到達できる距離を表します.右または下にのみ移動する必要があります.0はプロセスをブロックする終点ではなく、現在のセルの数値に従って常に右または下に移動します.一度踊るときは、Uターンしてはいけません.すなわち,1つの格子から右へジャンプする場合と下へジャンプする場合の2つしか存在しない.
プログラムを作成し、ルールに従って左上から右下に移動できるパス数を求めます.

に近づく

dpで近づく.

板[r][C]:(r,c)座標値

dp[r][c]:(r,c)座標に移動可能な経路数

dp[r][c] += if board[r-k][c]==k then dp[r-k][c], if board[r][c-k]==k then dp[r][c-k]

dp[r][c]は、(r,c)座標に移動可能な経路の個数として定義される.このように、dp[r][C]の値が回路基板(r,c)の回路基板内、左座標の値が(r,c)座標に移動可能な値であれば、その座標のdp値を求めることができる.

コード#コード#

bool isInBound(int boardSize, int r, int c){
    return 0<=r && r<boardSize && 0<=c && c<boardSize;
}

long long recurs(int boardSize, int r, int c){
    if(dp[r][c])
        return dp[r][c];

    dp[r][c] = 0;
    for(int k=1; k<10; k++){
        if(isInBound(boardSize, r-k, c) && board[r-k][c] == k)
            dp[r][c] += recurs(boardSize, r-k, c);
        if(isInBound(boardSize, r, c-k) && board[r][c-k] == k)
            dp[r][c] += recurs(boardSize, r, c-k);
    }

    return dp[r][c];
}

dp[0][0]を1に初期化し,到達座標呼び出しrecurs()関数を解くことができる.