题意分析

题目描述了一个 $n \times n$ 的游戏棋盘，每个方格内填充着一个非负整数（$0$-$9$）。游戏的目标是从棋盘的左上角（起点）出发，沿着合法的路径移动到右下角（终点）。移动规则如下：

1. 移动方向：只能向右或向下移动。
2. 步长限制：每个方格中的数字表示从该位置出发时必须移动的步长。例如，数字 $2$ 表示必须向右或向下移动 $2$ 步。
3. 边界限制：如果移动步长会导致超出棋盘边界，则该方向的移动是被禁止的。
4. 死路：数字 $0$ 表示死路，无法从该位置继续移动。

解题思路

关键点分析

1. 移动规则：

   • 只能向右或向下移动。
   • 移动步长由当前方格的数字决定。
   • 不能超出棋盘边界。
   • 数字 $0$ 表示无法移动。

2. 路径计数：

   • 需要计算从起点 $(0, 0)$ 到终点 $(n-1, n-1)$ 的所有合法路径数量。
   • 路径数量可能非常大（$< 2^{63}$），需要用 64 位整数存储。

3. 动态规划：

   • 使用动态规划（DP）来避免重复计算和暴力枚举。
   • 定义 $dp[i][j]$ 表示从 $(i, j)$ 到终点的路径数量。
   • 初始条件：$dp[n-1][n-1] = 1$（终点到自身的路径数为 $1$）。
   • 递推关系：
     • 如果当前方格为 $0$，则 $dp[i][j] = 0$。
     • 否则，$dp[i][j] = dp[i + \text{step}][j] + dp[i][j + \text{step}]$（需检查边界）。

解决步骤

1. 输入处理：

   • 读取棋盘数据，直到遇到 $-1$。
   • 对每个棋盘，初始化 $n \times n$ 的 DP 表。

2. 动态规划填充：

   • 从终点 $(n-1, n-1)$ 开始，逆向填充 DP 表。
   • 对于每个方格 $(i, j)$：
     • 如果 $(i, j)$ 是终点，$dp[i][j] = 1$。
     • 如果方格数字为 $0$，$dp[i][j] = 0$。
     • 否则，检查向右和向下移动的合法性，并累加路径数。

3. 输出结果：

   • 起点 $(0, 0)$ 的 DP 值即为答案。

算法复杂度

• 时间复杂度：$O(n^2)$，每个方格只需处理一次。
• 空间复杂度：$O(n^2)$，存储 DP 表。

#include <iostream>
#include <cstdio>

using namespace std;

int n, m, k, Max;
long long vis[110][110];
int Map[110][110];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

long long dfs(int x, int y) {
    if (x == n - 1 && y == n - 1) {     // Reached the destination
        return 1;
    }
    if (vis[x][y]) {
        return vis[x][y];
    }
    if (x < 0 || y < 0 || x >= n || y >= n || Map[x][y] == 0) {     // Out of bounds or blocked
        return 0;
    }
    vis[x][y] += dfs(x + Map[x][y], y) + dfs(x, y + Map[x][y]);  // Move right and down
    
    return vis[x][y];
}

int main() {
    while (scanf("%d", &n) != EOF) {
        if (n == -1) {
            break;
        }
        // Manually initialize vis array
        for (int i = 0; i < 110; ++i) {
            for (int j = 0; j < 110; ++j) {
                vis[i][j] = 0;
            }
        }
        char s[110];
        for (int i = 0; i < n; ++i) {
            scanf("%s", s);
            for (int j = 0; j < n; ++j) {
                Map[i][j] = s[j] - '0';
            }
        }
        printf("%lld\n", dfs(0, 0));
    }
    return 0;
}