【题解】帕斯卡的旅行

题目描述

　　在一个n×n方格的游戏板中，每个方格中有一个非负整数。游戏的目标是从游戏板的左上角沿任何合法路径移动到右下角。任何一个方格内的数字规定了离开本方格的一步必须移动的方格数。如果移动的一步越出了游戏板，则这个方向的移动是禁止的。每一步移动只能是向下或向右的。

 

输入格式

　　n+1行：

　　第一行是游戏板的行数n（4≤n≤34），接下来是n个数据行，每行含有n个0-9的数字，中间没有空格。

 

输出格式

　　在一行中输出从左上角到右下角的路径数（注意：输出的路径数使用长整型数据类型）。

 

输入样例

4

2331

1213

1231

3110

 

输出样例

3

 

题解

　　这里用$dp[i][j]$顺推$dp[i+a[i][j]][j]$和$dp[i][j+a[i][j]]$即可。

#include <iostream>
#include <cstdio>

#define MAX_N (34 + 5) 

using namespace std;

int n;
int a[MAX_N][MAX_N];
long long dp[MAX_N][MAX_N];

int main()
{
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            scanf("%1d", &a[i][j]);
        }
    }
    dp[1][1] = 1;
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            if(!a[i][j]) continue;
            if(i + a[i][j] <= n) dp[i + a[i][j]][j] += dp[i][j];
            if(j + a[i][j] <= n) dp[i][j + a[i][j]] += dp[i][j];
        } 
    }
    printf("%lld", dp[n][n]);
    return 0;
}