走迷宫(详细分析)

2023-12-15 03:22:25

目录

一、课题描述

输入样例:

输出样例:

二、需求分析

输入的形式和输入值的范围:

输出的形式:

程序所能达到的功能:

三、概要设计

四、流程图

五?、代码+详细注释

六、测试数据和结果


一、课题描述

以一个 m*n 的方阵表示迷宫,0 和 1 分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的最短通路,或得出没有通路的结论。

输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8

二、需求分析

本设计程序用C++ 编写,完成二维数组迷宫的生成,找到走出迷宫的最短路径,或者返回没有通路的结论。

  • 输入的形式和输入值的范围:

  • 输入格式:第一行包含两个整数 n 和 m。接下来 n行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。数据范围:1≤n,m≤100。
  • 输出的形式:

  • 输出一个整数,表示从左上角移动至右下角的最少移动次数。

???程序所能达到的功能:

? ? 1.找到一条从入口到出口的最短通路2.如果迷宫内没有通路,则返回没有通路的结论。

三、概要设计

1 )数据逻辑结构、存储结构分析:

(1 ) 数据逻辑结构:

在迷宫求解的问题中,我运用了队列这种线性结构来存储最新到达的地点,队头出队即表示该点走向下一个结点。

(2 )存贮结构分析:

在迷宫求解的问题中,我运用了队列这种顺序结构,队列在这个代码中的作用是实现广度优先搜索算法(BFS)。BFS是一种图遍历算法,用于在图或二维网格中寻找最短路径或解决某些问题。

2 )本程序包含2 个函数:

(1 )广度优先搜索算法函数bfs()

  1. 参数描述:

g[N][N]:存贮迷宫信息

d[N][N]:存贮各个点到起始点的路径长度

PII q[N*N],hh,tt:模拟队列,PII q[N*N]:存贮队列中的数据,hh:队头,tt:队尾

Dx:代表这个点在x轴的偏移量,dy:代表这个点在y轴的偏移量

  1. 功能描述

初始化队列:将起始点排入队列中,即{0,0}。

初始化d数组:将d数组初始化为-1,从而在bfs搜索时能判断出这个点是否被搜索过

初始化dx数组和dy数组:即存贮x和y上下左右移动时的偏移量

For循环判断:将这个点进行上下左右四次移动,如果它在我的二维数组迷宫里面(未超出范围)并且移动之后点的值等于0(能够通行)而且是第一次通过(最短路),我就将它入队,并且记录它距离下一个点的距离加1,然后就是一个循环过程,只要我的队里有元素,就说明还未找到最短路。

(2 )主函数main()

  1. 参数描述

M,n:代表m行n列的迷宫

Flag:判断迷宫中是否有通路

  1. 功能描述

初始化迷宫:输入m行n列的迷宫

判断返回值:将bfs得到的结果进行判断,如果我的迷宫出口距离起始点不是-1的话(已经被搜索到过),那我就返回最短路径,否则返回没有通路。

流程图

五?、代码+详细注释

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef pair<int, int>PII;

const int N = 110;
//定义一些全局变量
//n,m n行m列
//g数组 存贮迷宫
//d数组 存贮点到起始点的距离
//q二元组 存贮队列元素点的数据
int n, m;
int g[N][N];
int d[N][N];
PII q[N * N];
 
//重点!bfs的实现
int bfs()
{
    //队头hh,队尾tt
	int hh = 0, tt = 0;
    //队头起始点{0,0}
	q[0] = { 0,0 };

    //memset函数,将d数组初始化为-1,主要是用于后面判断此点是否被用过
	memset(d, -1, sizeof d);
    //将起始点距离初始化为0
	d[0][0] = 0;

    //用数组dx和dy分别存贮x和y和偏移量
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
    //只要我的队列中有元素,就说明广度搜索没搜索完
	while (hh <= tt)
	{
        //将队头元素弹出赋值给t
        //auto t其实就等于pair<int,int> t(auto 就是让系统自己猜出t的变量类型,不需要我写出冗杂的代码)
		auto t = q[hh++];
        //将队头弹出的点进行上下左右四次偏移
		for (int i = 0; i < 4; i++)
		{
            //t.first即指pair这个二元组前一个元素,t.second即后一个元素
            //这一步就是得到移动后x,y的坐标
			int x = t.first + dx[i], y = t.second + dy[i];
            //判断移动后的点是否能入队
            //x >= 0 && x < n && y >= 0 && y < m首先这个点不能超出我的迷宫边界
            //g[x][y] == 0 其次这个点得是我能通行的(即在这个迷宫上这个点的值为0)
            //d[x][y] == -1 由于我上面有过的初始化,所以d[x][y] == -1时代表这个点第一次被搜索
            //下一次搜索到这个点我就不要了,就不是最短路径了
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
			{
                //用d数组记录点到起始点的距离
				d[x][y] = d[t.first][t.second] + 1;
                //最后将bfs搜索到的点入队,进行下一次搜索
				q[++tt] = { x,y };
			}
		}
	}
    //最后返回终点距离起始点的距离
	return d[n - 1][m - 1];
}

int main()
{
    
	cin >> n >> m;

    //输入我的迷宫
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> g[i][j];

    //用flag接收bfs函数返回的值
    int flag = bfs();
    //如果返回的值等于-1的话,说明我的bfs并没有搜索到最后的出口,即这条迷宫没有通路
    //反之则有通路,并且是最短通路
    if (flag!=-1) cout << flag << endl;
    else cout << "此迷宫中,没有道路能走出去" << endl;

	return 0;
}

、测试数据和结果

测试数据1

测试结果:

测试数据2:

测试结果:

测试数据3:

测试数据4:

测试结果:

文章来源:https://blog.csdn.net/2301_79532295/article/details/134844001
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。