路径之谜

题目描述

小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n×nn×n 个方格。如下图所示。

按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 nn 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入描述

第一行一个整数 NN (0≤N≤200≤N≤20)，表示地面有 N×NN×N 个方格。

第二行 NN 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 NN 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出描述

输出一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯⋯

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

运行限制

• 最大运行时间：5s
• 最大运行内存: 256M

总通过次数: 12638  |  总提交次数: 16353  |  通过率: 77.3%

难度: 困难   标签: 2016, 国赛, DFS

骑士路径之谜：DFS算法解析与实现

问题分析

骑士从城堡西北角（左上角）出发，需到达东南角（右下角），移动规则如下：

1. ​​移动方式​​：横向或纵向移动（不能斜走或跳跃）
2. ​​箭靶机制​​：每到达新方格，需向正北（列箭靶）和正西（行箭靶）各射一箭
3. ​​路径约束​​：每个方格仅允许访问一次，且路径需满足给定的箭靶数字
4. ​​输出要求​​：输出用数字编号表示的路径（编号规则：行优先，从0开始）

代码展示：

#include <iostream>
#include <vector>
using namespace std;const int dx[4] = {0, 0, 1, -1};  // 右、左、下、上
const int dy[4] = {1, -1, 0, 0};  // 移动方向向量vector<int> path;          // 路径记录
vector<int> northTarget;   // 北箭靶（列靶）
vector<int> westTarget;    // 西箭靶（行靶）
vector<vector<bool>> visited;  // 访问标记
int n;                     // 城堡尺寸
bool found = false;        // 路径找到标志// DFS搜索函数
void dfs(int x, int y) {// 到达终点且箭靶归零if (x == n-1 && y == n-1) {for (int i = 0; i < n; i++) {if (northTarget[i] != 0 || westTarget[i] != 0) return;}found = true;return;}// 尝试四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];// 检查新位置合法性if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;if (visited[nx][ny]) continue;if (westTarget[nx] <= 0 || northTarget[ny] <= 0) continue;// 更新状态visited[nx][ny] = true;westTarget[nx]--;northTarget[ny]--;path.push_back(nx * n + ny);dfs(nx, ny);  // 递归搜索if (found) return;// 回溯恢复状态visited[nx][ny] = false;westTarget[nx]++;northTarget[ny]++;path.pop_back();}
}int main() {cin >> n;// 初始化数据结构northTarget.resize(n);westTarget.resize(n);visited.resize(n, vector<bool>(n, false));// 输入箭靶数据for (int i = 0; i < n; i++) cin >> northTarget[i];for (int i = 0; i < n; i++) cin >> westTarget[i];// 起点处理visited[0][0] = true;westTarget[0]--;        // 起点影响西墙第0行northTarget[0]--;       // 起点影响北墙第0列path.push_back(0);      // 加入起点编号dfs(0, 0);  // 开始搜索// 输出路径for (int i = 0; i < path.size(); i++) {cout << path[i] << (i < path.size()-1 ? " " : "\n");}return 0;
}

关键优化策略

1. ​​箭靶剪枝​​：移动前检查目标位置对应的行/列箭靶剩余值（值≤0时终止分支）
2. ​​实时回溯​​：发现无效路径时立即恢复箭靶计数和访问状态
3. ​​方向优先级​​：按右→左→下→上的顺序探索（优先水平移动加速靠近终点）
4. ​​终止条件​​：到达终点时验证所有箭靶恰好归零（northTarget[i]==0 && westTarget[i]==0）

复杂度分析

• ​​时间复杂度​​：最坏O(4n2)，实际通过箭靶剪枝大幅降低
• ​​空间复杂度​​：O(n2)（存储访问矩阵和路径）
• ​​运行效率​​：满足n≤20的约束，5秒时限内可完成

示例输入验证：
​​输入​​：4，2 4 3 4，4 3 3 3
​​输出​​：0 4 5 1 2 3 7 11 10 9 13 14 15
对应路径：
0(0,0)→4(1,0)→5(1,1)→1(0,1)→2(0,2)→3(0,3)→7(1,3)→11(2,3)→10(2,2)→9(2,1)→13(3,1)→14(3,2)→15(3,3)

注意事项

1. ​​起点特殊处理​​：初始位置(0,0)需直接更新箭靶并标记访问
2. ​​编号转换​​：位置(x,y)的编号计算为x*n + y
3. ​​路径唯一性​​：题目保证唯一解，找到路径后立即终止搜索
4. ​​边界检查​​：移动时需验证新位置在[0, n-1]范围内