题意分析

奶牛在5×5的数字网格中跳跃，每次只能向上下左右移动（不能斜向），经过5次跳跃后形成一个6位数字（允许前导零）。要求计算所有可能的不同6位数字的数量。

关键思路

1. 深度优先搜索（DFS）：
   从每个网格点出发，进行深度优先搜索，记录当前路径形成的数字。每次移动时，向四个方向扩展，直到形成6位数字为止。

2. 集合去重：
   使用集合（Set）存储所有生成的6位数字，利用集合的自动去重特性，最终集合的大小即为不同数字的数量。

3. 状态转移：

   • 状态参数：当前坐标(x, y)、已形成的数字长度step、当前数字num。
   • 转移逻辑：每次移动到相邻格子，将新数字位添加到num中（num = num * 10 + grid[tx][ty]），直到step = 6时将数字存入集合。

代码实现

#include <iostream>
#include <set>
using namespace std;

const int n = 5; // 5x5网格
int dt[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
set<int> numbers; // 存储不同的6位整数
int grid[n][n]; // 数字网格

// 深度优先搜索函数
void dfs(int x, int y, int step, int num) {
    if (step == 6) { // 形成6位数字时结束
        numbers.insert(num);
        return;
    }
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int tx = x + dt[i][0];
        int ty = y + dt[i][1];
        // 检查坐标是否在网格内
        if (tx >= 0 && tx < n && ty >= 0 && ty < n) {
            // 递归扩展数字长度，并更新当前数字
            dfs(tx, ty, step + 1, num * 10 + grid[tx][ty]);
        }
    }
}

int main() {
    // 读取网格数据
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    // 从每个格子出发进行DFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dfs(i, j, 1, grid[i][j]); // 初始数字为grid[i][j]，长度为1
        }
    }
    // 输出不同数字的数量
    cout << numbers.size() << endl;
    return 0;
}

代码解析

1. 输入处理：
   读取5×5的网格数据，存储在二维数组grid中。

2. DFS遍历：

   • 从每个格子(i, j)出发，初始数字为grid[i][j]，长度step=1。
   • 每次递归时，向四个方向移动，更新坐标(tx, ty)，并将新数字位拼接到num中（如当前数字为12，移动到数字3的格子后，新数字为123）。
   • 当step=6时，将完整的6位数字存入集合numbers中。

3. 去重与结果：
   集合numbers自动处理重复数字，最终输出集合的大小即为不同数字的数量。

复杂度分析

• 时间复杂度：每个格子作为起点，最多扩展$4^5$次（每次移动有4种方向，共5次跳跃）。总共有25个起点，因此总时间复杂度为 $25 \times 4^5 = 25 \times 1024 = 25600$，完全可接受。
• 空间复杂度：最坏情况下存储所有可能的6位数字（$10^6$种），但实际中由于网格限制，数量远小于此，集合的空间占用可控。

该方法通过深度优先搜索和集合去重，高效地解决了问题，确保了在合理时间内得到正确结果。