迷宫出口1430

  • 开发
  • 18

在这里插入图片描述

test
4
0 0 0 1
0 1 1 0
1 1 1 1
0 0 0 0
1 1 4 3

4
0 0 0 1
0 1 1 0
1 1 1 1
0 0 0 0
1 4 2 4

3
0 1 1
0 0 1
1 0 0
1 1 3 3

dfs解法

一.什么是dfs

刚开始学习解这类题目的时候，这是让我十分困惑的一个点。
搜索dfs出来的多是图的遍历、二叉树的遍历相关内容，花了挺大精力理解这些文章，对解这道题确实是有很大帮助。但是我想记录一下，单纯从这道题目出发的思考过程。

现在有这样一个迷宫，尝试一下从左下角到右上角，留意自己走过的路径。

人脑可以快速构图判断一条路行不行，计算机是一格格走的。
现在添加一些规则，你必须严格按照规则来走

  1. 从起点出发后，按照方向上左下右的顺序探索，能进则进。
2. 无路可走时原路回退直到有新格子可以走。
3. 除了回退时，已经访问过的格子不得再访问。
如果你能按照前面三条规则走到终点，恭喜，你已经学会了狭义的走迷宫dfs。

剩下的就是利用代码去实现这一过程。

代码会涉及到结构体、栈等，不了解的同学请查阅些资料吧（也可以用纯数组的方式实现，数组表示节点，实现栈等，个人感觉这么做没那么直观。学了工具就是拿来用的O(∩_∩)O）。栈改用队列、数组也可以，用什么实现的不是特别重要，感受深搜思路。

二.核心思路

  1. 地图用二维数组表示，可走的为0，障碍物为1。
  2. 探索格子四个方向（利用当下坐标加上方向增量计算下一格坐标）。
  3. 走过的格子得标记，需要一个等大小的数组，探索过的格子置1，防止重复访问。
  4. 记录路径，无路可走时要回退的，建一个栈（回退回撤的功能大多利用栈实现）。

1.地图的表示、输入

这些内容不多说了，重点讨论dfs（）函数的实现。
为了方便压栈搞个结构体，把yx坐标一起压进去。

#include<iostream>
#include<stack>
using namespace std;

// 方向增量，分别为yx
int dr[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};//	上下左右
struct Pyx { //	结构体用于存储坐标
	int y;
	int x;
};

string dfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
	cout<<"冲"; 
}
int main() {
	int n = 0;// 地图大小
	cin>>n;
	int map[100][100] = {0};//	地图

	for(int i = 0; i<n; i++) {//	输入要测试的地图 
		for(int j = 0; j<n; j++) {
			cin>>map[i][j];
		}
	}
	int ha,la,hb,lb;//	A和B坐标
	cin>>ha>>la>>hb>>lb;
	
	//	由题目推出左上角坐标是（1,1）实际（0,0） ，修正 
	Pyx start,end;
	start.y = ha-1;
	start.x = la-1;
	end.y = hb-1;
	end.x = lb-1;

	cout<<dfs(start,end,map,n);
	return 0;
}

我们先按照核心思路把该弄的东西弄弄（弄啥嘞）

string dfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
	bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
	visited[start.y][start.x] = true;// 将起点标记为已访问
	stack<Pyx> path;//	声明一个栈用来储存路径
	path.push(start);//	起点入栈 
	Pyx pyx_current =  start;//	创建节点储存当下节点坐标，开始时在起点 
	
}

2.搜索四个方向

接下来我们要去访问当下位置四个方向上是否有可行进的格子，
有可走的格子就拿来和终点比较一下。

string dfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
	bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
	visited[start.y][start.x] = true;// 将起点标记为已访问
	stack<Pyx> path;//	声明一个栈用来储存路径
	path.push(start);//	起点入栈 
	Pyx pyx_current =  start;//	创建节点储存当下节点坐标，开始时在起点 
	
	//有四个方向
	for(int i = 0; i<4; i++) {
		//	计算下一步坐标
		int next_y = pyx_current.y+dr[i][0];
		int next_x = pyx_current.x+dr[i][1];

		//	前四个条件约束边界，第五个条件查看不是障碍物，第六个条件判断没有访问过
		if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&
		        map[next_y][next_x] == 0 && !visited[next_y][next_x]) {

			if(next_y == end.y && next_x == end.x) {//	每发现一个可访问的点，和终点对比
				return "YES";
			}

			Pyx pyx_next = {next_y,next_x};//	创建节点储存下一步坐标
			path.push(pyx_next);//	将节点存入栈
			visited[next_y][next_x] = true;//	入栈了标记为已访问

			pyx_current = pyx_next;//	去到下个格子 
		}
	}
}

实际上，我们找到下一个能走的格子，就立马过去了。

			pyx_current = pyx_next;//	去到下个格子 
			break；//	跳出for循环。

用一个大循环不断重复这一动作。（停止条件可以后面再思考）

	while(1){
		//有四个方向
		for(int i = 0; i<4; i++) {
			//	计算下一步坐标
			int next_y = pyx_current.y+dr[i][0];
			int next_x = pyx_current.x+dr[i][1];
	
			//	前四个条件约束边界，第五个条件查看不是障碍物，第六个条件判断没有访问过
			if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&
			        map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
	
				if(next_y == end.y && next_x == end.x) {//	每发现一个可访问的点，和终点对比
					return "YES";
				}
	
				Pyx pyx_next = {next_y,next_x};//	创建节点储存下一步坐标
				path.push(pyx_next);//	将节点存入栈
				visited[next_y][next_x] = true;//	入栈了标记为已访问
	
				pyx_current = pyx_next;//	去到下个格子 
				break;//	跳出for循环
			}
		}
	}

自己捋一捋程序，目前只能走到图片这里，接下来要思考回退的事情

3.什么时候开始回退呢？

走到无路可走时。
我们设置一个布偶量has_unvisited 来记录是否有可访问点，默认为没有，所以每次循环开始要设为false。
存在可访问点时设为真（即满足for循环里的if语句）。
不存在可访问点则回退上一格（从栈里弹出当前点）

	while(1){
		bool has_unvisited = false;  // 用来标记是否还有未访问的节点，循环开始重置 
		pyx_current = path.top();//	回退到上一格子
		//有四个方向
		for(int i = 0; i<4; i++) {
			//	计算下一步坐标
			int next_y = pyx_current.y+dr[i][0];
			int next_x = pyx_current.x+dr[i][1];
	
			//	前四个条件约束边界，第五个条件查看不是障碍物，第六个条件判断没有访问过
			if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&
			        map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
				has_unvisited = true;//	存在可访问的格子 
				if(next_y == end.y && next_x == end.x) {//	每发现一个可访问的点，和终点对比
					return "YES";
				}
	
				Pyx pyx_next = {next_y,next_x};//	创建节点储存下一步坐标
				path.push(pyx_next);//	将节点存入栈
				visited[next_y][next_x] = true;//	入栈了标记为已访问
	
				pyx_current = pyx_next;//	去到下个格子 
				break;//	跳出for循环 
			}
		}
		if(!has_unvisited) { //	存在可访问节点就不弹栈
			path.pop();//	弹出当下节点
		}
	}
}

4.程序什么时候终止

当栈里啥也没有，表明我们把可走的路全部走了一遍，并且退回到了起点！

while(!path.empty()){//	栈空了， 还没找到终点说明走不到。

while结束了还没找到终点则返回NO

		while(!path.empty()){//	栈空了， 还没找到终点说明走不到。 
		bool has_unvisited = false;  // 用来标记是否还有未访问的节点，循环开始重置 
		pyx_current = path.top();//	回退到上一格子
		//有四个方向
		for(int i = 0; i<4; i++) {
			//	计算下一步坐标
			int next_y = pyx_current.y+dr[i][0];
			int next_x = pyx_current.x+dr[i][1];
	
			//	前四个条件约束边界，第五个条件查看不是障碍物，第六个条件判断没有访问过
			if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&
			        map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
				has_unvisited = true;//	存在可访问的格子 
				if(next_y == end.y && next_x == end.x) {//	每发现一个可访问的点，和终点对比
					return "YES";
				}
	
				Pyx pyx_next = {next_y,next_x};//	创建节点储存下一步坐标
				path.push(pyx_next);//	将节点存入栈
				visited[next_y][next_x] = true;//	入栈了标记为已访问
	
				pyx_current = pyx_next;//	去到下个格子 
				break;//	跳出for循环 
			}
		}
		if(!has_unvisited) { //	存在可访问节点就不弹栈
			path.pop();//否则弹出当前格子 
		}
	}
	return "NO";
}

这就结束了吗？
当时检查提交了很多遍都是错的

自己把所有解的情况都列了一种出来，发现当起点就在障碍物上，输出结果也是YES。
因为起点没经过检测，直接压栈的！！！
所以一开始直接对起点检测，起点在障碍物上后面的程序都不用执行。（出题人的弯弯肠子）

string dfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
	if(map[start.y][start.x]) {//检测起点
		return "NO";
	}
	
	bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
	visited[start.y][start.x] = true;// 将起点标记为已访问
	stack<Pyx> path;//	声明一个栈用来储存路径
	path.push(start);//	起点入栈 
	Pyx pyx_current =  start;//	创建节点储存当下节点坐标，开始时在起点
	
	while(!path.empty()){//	栈空了， 还没找到终点说明走不到。

三.全部代码

#include<iostream>
#include<stack>
using namespace std;

// 方向增量，分别为yx
int dr[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};//	上下左右
struct Pyx { //	结构体用于存储坐标
	int y;
	int x;
};

string dfs(Pyx start,Pyx end,int (&map)[100][100],int n) {
	if(map[start.y][start.x]) {
		return "NO";
	}
	
	bool visited[100][100] = {false};// 用于标记地图上的点是否访问过
	visited[start.y][start.x] = true;// 将起点标记为已访问
	stack<Pyx> path;//	声明一个栈用来储存路径
	path.push(start);//	起点入栈 
	Pyx pyx_current =  start;//	创建节点储存当下节点坐标，开始时在起点
	
	while(!path.empty()){//	栈空了， 还没找到终点说明走不到。 
		bool has_unvisited = false;  // 用来标记是否还有未访问的节点，循环开始重置 
		pyx_current = path.top();//	回退到上一格子
		//有四个方向
		for(int i = 0; i<4; i++) {
			//	计算下一步坐标
			int next_y = pyx_current.y+dr[i][0];
			int next_x = pyx_current.x+dr[i][1];
	
			//	前四个条件约束边界，第五个条件查看不是障碍物，第六个条件判断没有访问过
			if(next_y>=0 && next_y<n && next_x>=0 && next_x<n &&
			        map[next_y][next_x] == 0 && !visited[next_y][next_x]) {
				has_unvisited = true;//	存在可访问的格子 
				if(next_y == end.y && next_x == end.x) {//	每发现一个可访问的点，和终点对比
					return "YES";
				}
	
				Pyx pyx_next = {next_y,next_x};//	创建节点储存下一步坐标
				path.push(pyx_next);//	将节点存入栈
				visited[next_y][next_x] = true;//	入栈了标记为已访问
	
				pyx_current = pyx_next;//	去到下个格子 
				break;//	跳出for循环 
			}
		}
		if(!has_unvisited) { //	存在可访问节点就不弹栈
			path.pop();//否则弹出当前格子 
		}
	}
	return "NO";
}

int main() {
	int n = 0;// 地图大小
	cin>>n;
	int map[100][100] = {0};//	地图

	for(int i = 0; i<n; i++) {//	输入要测试的地图 
		for(int j = 0; j<n; j++) {
			cin>>map[i][j];
		}
	}
	int ha,la,hb,lb;//	A和B坐标
	cin>>ha>>la>>hb>>lb;
	
	//	由题目推出左上角坐标是（1,1）实际（0,0） ，修正 
	Pyx start,end;
	start.y = ha-1;
	start.x = la-1;
	end.y = hb-1;
	end.x = lb-1;

	cout<<dfs(start,end,map,n);
	return 0;
}
阅读全部

相关推荐

  4. 1432. 走出迷宫的最少步数

    2024-07-23 03:10:01       58 阅读

  9. CCF-走迷宫(bfs)

    2024-07-23 03:10:01       53 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 03:10:01       101 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 03:10:01       109 阅读

  9. 在Django里面运行非项目文件

    2024-07-23 03:10:01       87 阅读

  19. Python语言-面向对象

    2024-07-23 03:10:01       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-23 03:10:01       89 阅读

热门阅读

  1. 如何引入全局样式文件？

    2024-07-23 03:10:01       23 阅读

  3. 长短期记忆网络（LSTM）及其Python和MATLAB实现

    2024-07-23 03:10:01       25 阅读

  8. 大规模语言模型从理论到实践 大语言模型预训练数据

    2024-07-23 03:10:01       20 阅读

  9. python的open()函数

    2024-07-23 03:10:01       21 阅读

  11. 【过题记录】 7.22

    2024-07-23 03:10:01       18 阅读

  15. linux kernel 内核缓存回收的相关配置项

    2024-07-23 03:10:01       24 阅读

  17. Asp Net Web API 请求报错

    2024-07-23 03:10:01       19 阅读

  18. 欧鹏 数据库第二次作业

    2024-07-23 03:10:01       19 阅读

  23. FTP传输的两种模式的技术原理和应用

    2024-07-23 03:10:01       23 阅读

  26. mysql的不等于和null值问题

    2024-07-23 03:10:01       23 阅读

  28. 论c++中的GUI

    2024-07-23 03:10:01       21 阅读