POJ3050-Hopscotch(穷竭搜索：DFS)

题目描述

奶牛以一种非传统的方式玩起了儿童的跳房子游戏。与其跳进一个线性排列的带有数字的方块中，奶牛们在 x 轴和 y 轴平行的 5 x 5 矩形网格中创建了数字。

然后，它们灵巧地跳到网格中的任何一个数字，并向前、向后、向右或向左（不会对角线跳跃）跳到网格中的另一个数字。它们再次跳跃（遵循相同的规则）到一个数字（可能是已经访问过的数字）。

通过总共五次网格内跳跃，它们的跳跃形成了一个六位整数（可能像 000201 一样有前导零）。

确定以这种方式可以创建的不同整数的数量。

输入格式

第 1 行至第 5 行: 网格，每行五个整数。

输出格式

第1行: 可以构建的不同整数的数量。

输入输出样例 #1

输入 #1

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

输出 #1

15

提交链接

Hopscotch

思路分析

1. 从每个格子出发，进行深度优先搜索（DFS）

   目标是探索从当前位置出发跳 $5$ 步后形成的所有 $6$ 位数字组合

   由于可以走重复路径，不需要记录访问状态（visited）

2. 使用 set 来自动去重

   不同路径可能形成相同的数字，因此使用 set<int> 存储所有数字，避免重复计入

3. 递归出口为：跳了 $5$ 次（已经有 $6$ 位数字）

   此时把构造好的整数加入集合中即可

🧱 数据结构设计

g[6][6]：存储输入网格，编号从 $1$ 到 $5$

to[4][2]：方向数组，表示上下左右的位移

set<int> s：用于存储所有不同的 $6$ 位整数

🧩 核心代码解析

✅ 方向数组（上下左右）

int to[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

✅ DFS 搜索函数

void dfs(int x, int y, int num, int sum)
{if (num == 6) // 6 位数构造完毕{s.insert(sum); // 去重插入return;}for (int i = 0; i < 4; i++) // 尝试四个方向{int tx = x + to[i][0], ty = y + to[i][1];if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 5) // 判断是否出界dfs(tx, ty, num + 1, sum * 10 + g[tx][ty]); // 更新当前位置和累积的数字}
}

• $num$：当前数字的位数（已经构建了几位）

• $sum$：当前构建的数字（通过乘以 $10$ 拼接下一位）

• $tx$, $ty$：下一步跳的位置

✅ 主函数逻辑

for (int i = 1; i <= 5; i++)for (int j = 1; j <= 5; j++)cin >> g[i][j]; // 输入网格// 枚举每一个起点
for (int i = 1; i <= 5; i++)for (int j = 1; j <= 5; j++)dfs(i, j, 1, g[i][j]); // 从每个点出发，num=1表示已使用一个数字cout << s.size(); // 输出不同6位数的个数

📊 时间复杂度分析

起点数量：$25$ 个，每次 DFS 的路径数：$4^5=1024$，总路径：$25\ast 1024=25600$ 条路径

算法复杂度在 $10^4$ 级别

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <set>
#include <vector>
using namespace std;int to[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};int g[6][6];
set<int> s;void dfs(int x, int y, int num, int sum)
{if (num == 6){s.insert(sum);return;}for (int i = 0; i < 4; i++){int tx = x + to[i][0], ty = y + to[i][1];if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 5)dfs(tx, ty, num + 1, sum * 10 + g[tx][ty]);}
}int main()
{for (int i = 1; i <= 5; i++)for (int j = 1; j <= 5; j++)cin >> g[i][j];// 枚举每一个起点for (int i = 1; i <= 5; i++)for (int j = 1; j <= 5; j++)dfs(i, j, 1, g[i][j]);cout << s.size();return 0;
}