数据结构实验二：迷宫的求解

2024-07-12 07:20| 来源: 网络整理| 查看: 265

Exp02 迷宫的求解

Author: Maskros

实验目的

输入迷宫，得到从入口到出口的(最短)路径

实验内容与要求

迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。

实验内容和实验步骤

分别通过深度优先搜索 (dfs) 和广度优先搜索 (bfs) 两种方法来实现实验要求

大体思路： dfs O ( m ∗ n ) O(m*n) O(m∗n)？：结构体point 存储点的信息，maze[][]存图，visit[][]判断是否访问过，dir[4][2]用于存储四个方向，便于查找stack s 栈用于存储最终路径void dfs(int x,int y) 函数对坐标进行深度优先搜索，采用递归的思路，顺着一条路猛找，找不到返回上一级结点，直到找到为止。void printpoint() 函数用于打印路径void printmaze() 函数用于打印地图 bfs O ( m + n ) O(m+n) O(m+n)？：结构体node 存储点的信息，其中int l 表示从开始到该结点的距离，node father[][]数组用于存储当前节点的上一步是哪个结点，便于输出路径，其余变量同dfsqueue q 用于读入可走的路径，在bfs中使用bool check(int x,int y) 函数用于判断当前结点是否可走int bfs(node s) 函数，结束标志为队空，从当前结点依次遍历可走的方向，如果可以继续走就将可走结点入队，如果走到终点即返回最短路径长度string to_string(int s) 函数用于将int类型转为string类型，便于输出路径void print()函数根据father[][]从终点逆推打印路径输入形式：首先输出两个正整数 m m m , n n n , 表示迷宫的有 n n n 行 m m m 列，接下来输入迷宫序列, 1 表示可以通过, 0 表示不能通过。输出形式：以 bfs 实现的为例，首先输出最短路长度 l m i n l_{min} lmin , 接下来以 ( x i , x i ) (x_i,x_i) (xi,xi) -> $(x_j,y_j) $ … 表示这条路径，最后输出地图，用* 表示走过的路使结果更加直观；没有路径则输出-1 dfs实现(求一条路径) //presented by Maskros - 2021/04/21 //dfs #include using namespace std; int m,n; char maze[20][20]; //map int vis[20][20]={0}; //check if visited int dir[4][2]={ //four directrions {0,-1},{-1,0},{0,1},{1,0} }; char ans[20][20]; struct point{ int x,y; //coordinate char d; //Record direction point(){}; point(int a,int b,char c):x(a),y(b),d(c){} }pp; char check(int x,int xx,int y,int yy){ //Check the direction of the path if(xx>x) return 'D'; if(xxy) return 'R'; if(yy=m||x=n||y

【本文地址】

数据结构实验二：迷宫的求解

数据结构实验二：迷宫的求解

今日新闻

推荐新闻