一个人的巴黎

用户名：uq_36478041918

访问量：14980

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：360

奖学金，运用sort函数对结构体类型排序
浏览：283

奖学金，运用sort函数对结构体类型排序
浏览：148

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （Java代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

路径之谜(迷宫问题 DFS 每步详细解答)

　　作者: 一个人的巴黎　　　　发表时间：2022-01-25 10:59:29 浏览：692　|　评论：1　

原题链接：蓝桥杯2016年第七届真题-路径之谜

|   |(x-1,y)|   |
| ------------ | ------------ | ------------ |
|(x,y-1)|**( x , y )**|(x,y+1)|
|   |(x+1,y)|   |

```cpp
#include<iostream>
using namespace std;
int n;
int a[20], b[20];//a数组为自西向东的靶数，b数组为自北向南的靶数
int arr[20][20];//格子标记，按题目要求，0,1,2,3,4,...,n-1
int vis[20][20] = { 0 };//标记该点是否被走过
int top;//栈顶
int stack[20];//调用栈，存储路径，即答案
int dx[4] = { 1,0,-1,0 };//方向坐标，对应下左上右（见上图)
int dy[4] = { 0,-1,0,1 };//方向坐标，对应下左上右
bool check()//检查靶子上的靶数是否为0，因为采用的减法，所以为0，说明路径正确，否则说明路径不正确
{
	for (int i = 0; i < n; i++)
	{
		if (a[i] != 0 || b[i] != 0)
			return false;
	}
	return true;
}
void dfs(int x, int y, int step)
{
	if (a[y] < 0 || b[x] < 0)//剪枝  如果要射的箭数小于0了，那么就说明多射了一箭，再继续走下去就不可能符合题目的要求了
		return;
	if (x == n - 1 && y == n - 1)//终止条件，到达最后一个格子，坐标为(n-1,n-1)
	{
		if (check())//靶数对应正确，则输出，否则继续递归
		{
			for (int i = 0; i < top; i++)
				cout << stack[i] << " ";
			cout << endl;
		}
		return;
	}
	for (int i = 0; i < 4; i++)//下一步往哪个方向走(共4个方向)
	{
		int tx, ty;//下一点的坐标
		tx = x + dx[i];
		ty = y + dy[i];
		if (vis[tx][ty] == 0 && tx >= 0 && tx < n && ty >= 0 && ty < n)//未被访问，且未超出格子
		{
			vis[tx][ty] = 1;//标记为访问
			stack[top++] = arr[tx][ty];//格子对应标记入栈
			a[ty]--;//靶数对应减1
			b[tx]--;
			dfs(tx, ty, step+1);//从当前坐标继续向后走(递归调用)
			a[ty]++;//回溯(靶数对应加1)
			b[tx]++;
			top--;//出栈
			vis[tx][ty] = 0;//标记为未访问
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)//输入靶数
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cin >> b[i];
	for (int i = 0,k=0; i < n; i++)//初始化格子标记0,1,2,3,4,...,n-1
		for (int j = 0; j < n; j++)
			arr[i][j] = k++;
	//从第一个格子开始，将第一个格子做一些初始化
	vis[0][0] = 1;//标记为访问
	stack[0] = arr[0][0];//入栈
	top = 1;//栈内元素个数为1
	a[0]--;//对应靶数减1
	b[0]--;
	dfs(0, 0, 1);//从坐标(0,0)开始向后走
	return 0;
}
```

0.0分

12 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

KenHe

第65行，a[0][0]改为arr[0][0]

2022-03-10 20:50:37

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （Java代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

路径之谜(迷宫问题 DFS 每步详细解答)

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【明明的随机数】（C语言代码）

愚蠢的摄影师（C++代码）

C二级辅导-同因查找（C语言代码）

复数求和（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

矩阵的对角线之和（C语言代码）

1073题解

三进制小数（C语言代码）

字符串对比（C++代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （Java代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

路径之谜(迷宫问题 DFS 每步详细解答)

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【明明的随机数】 （C语言代码）

愚蠢的摄影师 （C++代码）

C二级辅导-同因查找 （C语言代码）

复数求和 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

矩阵的对角线之和 （C语言代码）

1073题解

三进制小数 （C语言代码）

字符串对比 （C++代码）

　　评论区

【明明的随机数】（C语言代码）

愚蠢的摄影师（C++代码）

C二级辅导-同因查找（C语言代码）

复数求和（C语言代码）

矩阵的对角线之和（C语言代码）

三进制小数（C语言代码）

字符串对比（C++代码）