（C++）数据结构实验二——迷宫问题BFS算法迷宫BFS算法迷宫QueueBottom.h

57 阅读 0 评论 38 点赞

我是靠谱客的博主大气过客，最近开发中收集的这篇文章主要介绍（C++）数据结构实验二——迷宫问题BFS算法迷宫BFS算法迷宫QueueBottom.h，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

BFS算法迷宫

#include <iostream>
#include <string>
//#include <queue>
#include "QueueBottom.h"
#include <fstream>
using namespace std;
#include <iomanip>
#include <Windows.h>
#include <time.h>
clock_t start,finish;
//改变字体颜色
void setColour(int x){
HANDLE h = GetStdHandle (-11);
SetConsoleTextAttribute(h,x);
}
//四个方向
int maze[100][100], past_footprint[100][100];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//存储最终的路径的数组
int final_array[100][100];
int printmaze[100][100];
int second_printmaze[100][100];
int whole_step;
struct point
{
int x;
int y;
int step;
};
queue<point> now_footprint;
queue<point> second_footprint;
void printMaze(int& endx, int& endy, int& startx, int& starty, int& length, int& width, string mapname)
{
ifstream first(mapname, ios::in);
if (!first.is_open())
{
cout << "Error: opening file fail" << endl;
system("pause");
exit(1);
}
while (!first.eof())
{
first >> length >> width ;
for (int i = 0; i < length; i++)
for (int j = 0; j < width; j++)
first >> maze[i][j];
first
>> endx >> endy >> startx >> starty;
}
// //之后可以改成从txt文件中读取
// //输入竖向长度x
// cout << "Please Enter the length of maze:" << endl;
// cin >> length ;
// //输入横向长度y
// cout << "Please Enter the width of maze:" << endl;
// cin >> width ;
// //输入迷宫的形状，1为通路，2为障碍，没有边框
// cout << "Enter the whole maze:" << endl;
// for (int i = 0; i < length; i++)
//
for (int j = 0; j < width; j++)
//
cin >> maze[i][j];
// //输入迷宫的起点	
// cout << "Please Enter the start of maze" << endl;
// cin >> endx >> endy ;
// //输入迷宫的终点
// cout << "Please Enter the end of maze" << endl;
// cin >> startx >> starty ;
}
void findRoad(int startx, int starty, int endx, int endy, int length, int width)
{
//BFS
//队首元素初始化
point start;
start.x = startx;
start.y = starty;
start.step = 0;
int tag = 1;
now_footprint.push(start);
past_footprint[startx][starty] = 1;
cout << "The Map before function :" << endl;
cout << " 1 for road; 2 for wall " << endl << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
cout << maze[m][n] << "
";
}
cout << endl;
}
cout << endl;
//终点标志
int flag = 0;
while(!now_footprint.empty())
{
//将该队列的首元素的 x y 分别赋予临时的 x y
int x = now_footprint.front().x;
int y = now_footprint.front().y;
//判断该队列的元素是否与终点匹配
printmaze[x][y] = now_footprint.front().step;
whole_step = now_footprint.front().step;
if(x==endx && y==endy)
{
flag = 1;
cout << "The shortest road from start to end is : "<< now_footprint.front().step << endl ;
cout << "It start at "<< startx << " " << starty << endl;
cout << "It end at " << endx << " " << endy << endl;
cout << "It start with number 0 and end with number " <<now_footprint.front().step << endl;
break;
}
//探路拓展循环
for(int k = 0; k <= 3; k++)
{
//创建临时变量tx ty
int tx,ty;
//按下 右 上 左的顺序去探路
tx = x + dx[k];
ty = y + dy[k];
if(maze[tx][ty] == 1 && past_footprint[tx][ty] == 0)
{
//若地点为未探索的点，则创建一个临时变量temp，将它入队
point temp;
temp.x = tx;
temp.y = ty;
temp.step = now_footprint.front().step + 1;
now_footprint.push(temp);
//并设置为已访问
past_footprint[tx][ty] = 1;
}
}
//将已经拓展完的首节点出队
now_footprint.pop();
}
//若找不到终点，则返回no answer
if (flag == 0)
cout << "No answer" << endl;
//将出口置为特殊符号
//因为我的vscode会乱码所以只能暂时改成颜色标识符 :D
setColour(12);
cout << setw(4) <<"#";
setColour(15);
cout << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
//需要包含头文件iomanip
//让每一个输出的宽度都为4
cout<<setw(4)<<printmaze[m][n];
//下面这行代码可以使得输出的字符左对齐
//<<setiosflags(ios::left)
//cout << printmaze[m][n] << "
";
}
cout << endl;
}
cout << endl;
}
void again_findRoad(int startx, int starty, int endx, int endy, int length, int width)
{
for(int i = 0; i <= length; i++)
for(int j = 0; j <= width; j++)
past_footprint[i][j] = 0;
point start;
start.x = endx;
start.y = endy;
start.step = 0;
int printmaze[100][100];
int tag = 1;
second_footprint.push(start);
past_footprint[endx][endy] = 1;
int flag = 0;
while(!second_footprint.empty())
{
int x = second_footprint.front().x;
int y = second_footprint.front().y;
second_printmaze[x][y] = second_footprint.front().step;
if(x==startx && y==starty)
{
flag = 1;
cout << "The shortest road from start to end is : "<< second_footprint.front().step << endl ;
cout << "It start at "<< endx << " " << endy << endl;
cout << "It end at " << startx << " " << starty << endl;
cout << "It start with number 0 and end with number " <<second_footprint.front().step << endl;
break;
}
for(int k = 0; k <= 3; k++)
{
int tx,ty;
tx = x + dx[k];
ty = y + dy[k];
if(maze[tx][ty] == 1 && past_footprint[tx][ty] == 0)
{
point temp;
temp.x = tx;
temp.y = ty;
temp.step = second_footprint.front().step + 1;
second_footprint.push(temp);
past_footprint[tx][ty] = 1;
}
}
second_footprint.pop();
}
cout << endl;
for(int m = 0; m < length;m++)
{
for(int n = 0; n < width;n++)
{
cout<<setw(4)<<second_printmaze[m][n];
}
cout << endl;
}
cout << endl;
}
void print_final_road(int length, int width, int step)
{
//step = whole_step;
for(int m = 0; m < length;m++ )
for(int n = 0; n < width;n++ )
{
if(printmaze[m][n] + second_printmaze[m][n] == step)
{
final_array[m][n] = 1;
}
}
for(int m = 0; m < length; m++ )
{
for(int n = 0; n < width; n++ )
{
// final_array[m][n] = printmaze[m][n] + second_printmaze[m][n] ;
cout << setw(4) << final_array[m][n];
}
cout << endl;
}
}
int main()
{
//定义变量
string mapname;
int endx, endy, startx, starty, width, length, afterendx, afterendy, aftertag;
//选择地图的号码
int tag;
while(1)
{
cout << "Please Choose the Map of CityPark : "<< endl;
cout << "Press 0 to exit"
<< endl;
cout << "-1:ClearScreen
0:Exit"
<< endl;
cout << "1:Shenzhen
2:GuangZhou " << endl;
cout << "3:BeiJing
4:ShangHai	" << endl;
cin >> tag;
cout << endl;
switch (tag)
{
case 1:
{
/*要计算时间的代码*/
mapname = "ShenZhenMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
start=clock();
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
finish=clock();
print_final_road(length,width,whole_step);
double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"ntime cost: "<<totaltime<<"seconds!"<<endl;
break;
}
case 2:
{
mapname = "GuangZhouMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 3:
{
mapname = "BeiJingMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 4:
{
mapname = "ShangHaiMap.txt";
printMaze(endx, endy, startx, starty, length, width, mapname);
findRoad(endx, endy, startx, starty, length, width);
again_findRoad(endx, endy, startx, starty, length, width);
print_final_road(length,width,whole_step);
break;
}
case 0:
{
cout << "Exit" << endl;
system("pause");
exit(1);
}
case -1:
{
system("cls");
break;
}
default:
break;
}
}
// printMaze(endx, endy, startx, starty, length, width);
// findRoad(endx,endy,startx,starty,length,width);
system("pause");
return 0;
}

BFS算法迷宫

#include<iostream>
using namespace std;
#include <time.h>
//地图数组，用来存储迷宫
int map[50][50];
bool visit[50][50];
int ans[250];
int res[250];
int tmp[250];
int k,Min,len;
//以下为增加内容
#include <fstream>
int length, width, startx, starty, endx, endy;
string mapname;
//判断方向的数组
int X[4]={-1,1,0,0};
int Y[4]={0,0,-1,1};
clock_t start,finish;
void readTxt(string mapname)
{
ifstream first(mapname, ios::in);
if (!first.is_open())
{
cout << "Error: opening file fail" << endl;
system("pause");
exit(1);
}
while (!first.eof())
{
first >> length >> width ;
for (int i = 0; i < length; i++)
for (int j = 0; j < width; j++)
{
first >> map[i][j];
visit[i][j]=false;
}
first >> startx >> starty >> endx >> endy ;
}
}
void dfs(int startx,int starty,int step,int k){
int x = startx;
int y = starty;
//判断当前格子的xy是否在0~5范围内
//若否则直接返回
//这个判断条件可以防止边界越界的情况 如x = -1, y = 0
if(x>=length||x<0||y>=width||y<0)return;
//当该点走过，则退出该层递归
if(visit[x][y])return;
//当该点为墙，则退出该层递归
if(map[x][y]==1)return;
//当xy为终点坐标时执行
if(x==endx&&y==endy){
if(step<Min){
ans[k]=x*10+y;
//将步数用Min存储，用于下次第二次通路的长度比较
Min=step;
for(int i=0;i<=k;i++){
res[i]=ans[i];
}
//全局变量，用于打印路径
len=k;
}
return;
}
//将走过的地方置为true
visit[x][y]=true;
ans[k]=x*10+y;
//使用递归来判断某一方向是否能走
for(int i=0;i<4;i++){
dfs(x+X[i],y+Y[i],step+1,k+1);
}
//注意此语句非常关键，既然找最短，则就需要不断
回溯，因此需要将原来访问过的标记清除
visit[x][y]=false;
//回溯的时候置空，还原
//当回溯到有分叉路的地方的时候，会走for循环中没有走过的路，同时不会影响这次的寻路
//添加该语句后就能从两条路线中选出相对较短的一条
}
int main(){
//cin >> length >> width >>startx >> starty >> endy >> endx;
//设定一个极大的值，使得第一次必然进入if循环
Min = 9999;
//存入输入的地图
// for(int i=0;i<length;i++){
//
for(int j=0;j<width;j++){
//
cin>>map[i][j];
//
visit[i][j]=false;
//
}
// }
readTxt("BeiJingMap.txt");
//dfs执行
start=clock();
dfs(startx,starty,1,0);
finish=clock();
//打印地图
for (int i = 0; i < length; i++)
{
for (int j = 0; j < width; j++)
{
cout << map[i][j] << " ";
}
cout << endl;
}
cout << endl;
//输出res中存储的坐标
for(int i=0;i<=len;i++){
cout<<"("<<res[i]%10<<", "<<res[i]/10<<")"<< "->" ;
if(i % 5 == 0)
cout << endl;
}
double totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"ntime cost: "<<totaltime<<"seconds!"<<endl;
system("pause");
return 0;
}
/*
10 10
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 0
0 1 0 1 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0 0
0 1 0 0 0 1 0 1 1 1
0 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 1 1 0
0 1 0 0 0 1 0 0 1 0
0 1 1 1 1 1 0 1 1 0
0 0
9 9
*/

1.两个迷宫均要在当前目录下创建txt文件
BFS是以1和2组成迷宫
DFS是以0和1组成迷宫

2.DFS没有使用stack而只是使用了数组，BFS中使用了queue，同时实现了底层。
代码如下

QueueBottom.h


#include <iostream>
using namespace std;
//模板结构体，可以适用于任何类型
template <typename T>
struct node{
T data;
node *next;
//构造函数初始化next和data值
node(){
next=NULL;
}
//new创建node结点的时候可以选择是否有初值
node(T x){
data=x;
next=NULL;
}
};
//模板类，可以适用于任何类型
template <typename T>
class queue{
private :
node<T> *head,*tail;
int len=0;
public :
queue(){
node<T> *temp=new node<T>();
head=tail=temp;
len=0;
}
//Q.size(); 返回该队列的长度
int size(){
return len;
}
//Q.empty(); 返回该队列是否为空
bool empty(){
if(len==0) return true;
return false;
}
//头元素
T& front(){
if(len) return head->next->data;
}
//尾元素
T& back(){
if(len) return tail->data;
}
void pop(){
if(len) {
head=head->next;
len--;
}
}
void push(const T a){
node<T> *temp=new node<T>(a);
tail->next=temp;
//？
tail = temp;
temp = NULL;
len++;
}
};
// int main(){
//
// Queue<string> Q;
//
// Q.push(string("abc1"));
//
// Q.push(string("abc2"));
//
// Q.push(string("abc3"));
//
// cout<<Q.front()<<endl;
//
// cout<<Q.back()<<endl;
//
// Q.pop();
//
// cout<<Q.front()<<endl;
//
// cout<<Q.back()<<endl;
//
system("pause");
//
return 0;
// }