当前位置：首页 > news >正文

【DFS/回溯算法】2016年蓝桥杯真题之路径之谜详解

news 来源：原创 2025/9/4 11:59:53

1.题目描述：

输入格式

输出格式

2.题解：

3.详细c++代码

1.题目描述：

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

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

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

按习俗，骑士要从西北角走到东南角。

可以横向或纵向移动，但不能斜着走，也不能跳跃。

每走到一个新方格，就要向正北方和正西方各射一箭。

（城堡的西墙和北墙内各有 n 个靶子）

同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？

有时是可以的，比如如图中的例子。

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

输入格式

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

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

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

输出格式

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

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

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

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

2.题解：

本题实质上是个DFS问题，根据给定的已知条件：北边和西边箭靶上箭的个数，逆推出路径。可以正向dfs，即设定两个空数组，每走过一个格子北面和西面的箭靶各加1。但在这道题更适合的方法是认为是一道拔箭问题，即每走过一个格子北面和西面的箭靶各减1，条件判断为：不能越界，不能走已经走过的格子，不能走已经满足箭靶上箭个数的格子。接下来设定check函数，用于判断是否走到了终点且满足每个箭靶的数量全部为0（全部拔光了）不满足则返回false，若满足条件，将保存的路径坐标转化为题目要求的输出格式，并返回false（原路恢复原样返回），若未到达终点，返回true。在主体的dfs函数中，首先用check函数检查是否到达了终点（false则return，回到上一层进行回溯，true则跳到else语句）else语句中首先对现有坐标进行上下左右的移动，按循环顺序选择符合条件判断的一个方向移动，接着进行拔箭，保存路径和标记已走过。然后进行递归dfs()进入下一层，在这之后设定回溯初始化，和递归的操作相反，放箭，删除路径和标记未走过，这里的代码是在dfs()执行完之后再去执行的，dfs()执行完说明最下层上下左右尝试过都不行一直return回溯到这一层。main函数里接受输入的数据。对于起点，由于进入dfs的点默认都是经过拔箭，保存路径和标记已走过处理的，因此要在main中提前处理。

3.详细c++代码

#include<bits/stdc++.h>
using namespace std;struct ball//结果路径坐标容器 
{int first;//横坐标 int second; //纵坐标 
}; int n;//行列数const int N=30; 
int row[N];//记录北边靶子的箭数 
int col[N];//记录西边靶子的箭数 
bool flag[N][N]; //上下左右的方向 
int ax[4]={0,1,-1,0};
int ay[4]={1,0,0,-1};//用来保存路径 ，xy对 
vector<ball> res;bool pd(int dx,int dy)//判断是否符合条件（不能越界，不能走已经走过的格子，不能走已经满足箭靶上箭个数的格子） 
{if(flag[dx][dy]==1)return false;if(dx<0)return false;if(dx>n-1)return false;if(dy<0)return false;if(dy>n-1)return false;if(row[dy]<=0)return false;if(col[dx]<=0)return false;return true;
}bool check(int dx,int dy)//仅当走到终点时使用：检查箭是否全部拔光，若全部拔光输出结果。不管怎么样全部return false（用来回溯） 
{if(dx==(n-1)&&dy==(n-1)){for(int i=0;i<n;i++){if(row[i]!=0)return false; //北面的箭全部拔光 }for(int i=0;i<n;i++){if(col[i]!=0)//西面的箭全部拔光 return false; }for(int i=0;i<res.size();i++)//按照输出格式输出结果 {int hx=res[i].first;int hy=res[i].second;int sum=n*hx+hy;cout<<sum<<" ";}return false;}return true;
}void dfs(int dx,int dy)
{if(check(dx,dy)==false)//检查走到终点时路径是否正确 {return;//回溯返回 }else{for(int i=0;i<4;i++){int x=dx+ax[i];int y=dy+ay[i];if(pd(x,y)==false) //检查是否符合条件 {continue;}else{flag[x][y]=1;row[y]--;col[x]--;res.push_back({x,y});//拔箭，保存路径和标记已走过dfs(x,y);//递归 res.pop_back();row[y]++;col[x]++;flag[x][y]=0;//回溯返回后恢复原状 } }}
}int main()
{//接受数据 cin>>n; for(int i=0;i<n;i++){cin>>row[i];} for(int i=0;i<n;i++){cin>>col[i];} //对于起点，由于进入dfs的点默认都是经过拔箭，保存路径和标记已走过处理的，因此要在main中提前处理flag[0][0]=1;col[0]--;row[0]--;res.push_back({0,0});dfs(0,0);return 0;}

感谢大家的观看！！！别忘记点赞哦！！！

1.题目描述：

输入格式

输出格式

2.题解：

3.详细c++代码

相关文章：