李华

用户名：2645479600

访问量：18654

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1127

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：921

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1572

你可能喜欢

蓝桥杯2016年第七届真题-路径之谜-题解(C++代码)---常规的深搜

　　作者: 李华　　　　发表时间：2020-03-31 17:53:21 浏览：416　|　评论：0　

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

解题思路:
1.第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
　第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
 　这是题目的条件。其实所谓箭靶上的数字就是走到终点的路径，途中所有点访问某行某列的次数
2.知道了箭靶上的数字是什么意思之后，就可以开始dfs了。从左上角的格子开始深搜，当走到了终点，并且行列访问情况与箭靶上的数字符合，就说明找到了答案
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[25][25],vis[25][25],n,flag;	//地图 
int r[25],c[25];	//分别代表行和列
vector<int> vec;	//用于记录路径 
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};	//上下左右 
int walk_r[25],walk_c[25];
int check()	//检验访问情况是否等于输入 
{
	for(int i=0;i<n;i++)
	{
		if(walk_r[i]!=r[i])	return 0;
		if(walk_c[i]!=c[i])	return 0;
	}
	return 1;
}
int in(int x,int y)	//判断是否出界 
{
	if(x>=0&&x<n&&y>=0&&y<n)	return 1;
	return 0;
}
void dfs(int x,int y)
{
	if(flag==1)	return;
	if(x==n-1&&y==n-1&&check())	//如果走到了终点，并且行列访问情况等于输入
	{
		flag=1;	//如果搜到了答案，后面就不需要再搜了
		for(int i=0;i<vec.size();i++)
		{
			cout << vec[i] << " ";
		}
		return;
	}
	for(int i=0;i<4;i++)	//上下左右
	{
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty)&&vis[tx][ty]!=1)	//如果没有超界并且没有往回走
		{
			vis[tx][ty]=1;
			walk_r[tx]++;
			walk_c[ty]++;
			vec.push_back(tx*n+ty);	//该格子进入路径数组
			dfs(tx,ty);
			vis[tx][ty]=0;
			walk_r[tx]--;
			walk_c[ty]--;
			vec.pop_back();	//回溯 
		} 
	} 
}
int main()
{
	cin >> n;
	for(int i=0;i<n;i++)	//读入列访问情况 
	{
		cin >> c[i];
	}
	for(int i=0;i<n;i++)	//读入行访问情况 
	{
		cin >> r[i];
	}
	walk_r[0]=1;
	walk_c[0]=1;	//第一个格子访问情况置一 
	vec.push_back(0);
	vis[0][0]=1;
	dfs(0,0);	//当前的坐标是(0,0), 行标记情况，列标记情况 
	return 0;
}
```

0.0分

5 人评分

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

李华

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

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

台球碰撞（C++代码）

printf基础练习2 （C语言代码）

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

蓝桥杯2016年第七届真题-路径之谜-题解(C++代码)---常规的深搜

评论区

精彩推荐

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

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

打水问题（C语言代码）

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

WU-输出正反三角形（C++代码）

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

C语言考试练习题_一元二次方程（C语言代码）

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

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

【矩阵】（C++代码）

李华

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

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

台球碰撞 （C++代码）

printf基础练习2 （C语言代码）

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

蓝桥杯2016年第七届真题-路径之谜-题解(C++代码)---常规的深搜

评论区

精彩推荐

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

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

打水问题 （C语言代码）

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

WU-输出正反三角形 （C++代码）

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

C语言考试练习题_一元二次方程 （C语言代码）

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

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

【矩阵】 （C++代码）

弟弟的作业（C语言代码）

台球碰撞（C++代码）

　　评论区

打水问题（C语言代码）

WU-输出正反三角形（C++代码）

C语言考试练习题_一元二次方程（C语言代码）

【矩阵】（C++代码）