开发者社区> prime7> 正文

迷宫求解非递归 DFS BFS(应用栈和队列)

简介:
+关注继续查看

栈和队列的应用对迷宫问题求解 没有递归 自己手动建的栈和队 并且输出路径 DFS的路径就是

栈中的坐标 BFS的路径在队又开了一个域存上一层的base值 语言还是用的C++ 感觉比C的封装性好很多

充分体会了一下DFS一边比BFS快 但是BFS是最优解而DFS可能不是最优解

 

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Maze_size 100 //定义迷宫最大值
class Maze
{
public:
    char Maze_map[Maze_size][Maze_size];
    bool Maze_map_bj[Maze_size][Maze_size];
    int stack[Maze_size][2],top;//栈 栈顶指针
    int queue[Maze_size][3],base,qtop;//队列 0 1存坐标 2记录路径 对首指针 队尾指针
    int length,wide;//迷宫长,宽(竖,横)
    int startx,starty;//起点坐标
    int step[4][2];
    Maze();//初始化迷宫
    void input();//从键盘输入
    bool DFS();//利用栈深度优先遍历
    bool BFS();//利用队列广度优先遍历
    void outputDFSmap();//输出深度优先遍历路径
    void outputBFSmap();//输出广度优先遍历路径
};

Maze::Maze()//初始化
{
    length=wide=0;
    startx=starty=0;
    step= {{0,1},{0,-1},{1,0},{-1,0}};
    top=0;
}

void Maze::input()//输入
{
    do
    {
        cout<<"input length and wide of maze(length>0,wide>0)"<<endl;
        cin>>length>>wide;
    }
    while(length<=0||wide<=0);
    cout<<"input maze"<<endl;
    for(int i=0; i<length; i++)
        for(int j=0; j<wide; j++)
        {
            cin>>Maze_map[i][j];
            if(Maze_map[i][j]=='S')
                startx=i,starty=j;
        }
    cout<<"input end"<<endl;
}

bool Maze::DFS()
{
    top=0;
    memset(Maze_map_bj,0,sizeof(Maze_map_bj));
    stack[++top][0]=startx,stack[top][1]=starty;
    Maze_map_bj[startx][starty]=1;
    while(top!=0)
    {
        int x=stack[top][0],y=stack[top][1];
        for(int i=0; i<4; i++)
            if(Maze_map[x+step[i][0]][y+step[i][1]]=='E')
                return 1;
        bool flag=0;
        for(int i=0; i<4; i++)
            if(Maze_map[x+step[i][0]][y+step[i][1]]=='.'&&!Maze_map_bj[x+step[i][0]][y+step[i][1]])
            {
                stack[++top][0]=x+step[i][0],stack[top][1]=y+step[i][1];
                Maze_map_bj[x+step[i][0]][y+step[i][1]]=1;
                flag=1;
                break;
            }
        if(flag)
            continue;
        top--;
    }
    return 0;
}

void Maze::outputDFSmap()
{
    if(!DFS())
    {
        cout<<"maze bu neng zou = = "<<endl;
        return ;
    }
    char newmap[Maze_size][Maze_size];
    for(int i=0; i<length; i++)
        for(int j=0; j<wide; j++)
            newmap[i][j]=Maze_map[i][j];
    for(int i=2; i<=top; i++)
        newmap[stack[i][0]][stack[i][1]]='*';
    cout<<"DFS:"<<endl;
    for(int i=0; i<length; i++)
        for(int j=0; j<wide; j++)
        {
            cout<<newmap[i][j];
            if(j==wide-1)
                cout<<endl;
        }
    cout<<endl;
}

bool Maze::BFS()
{
    base=0,qtop=1;
    memset(Maze_map_bj,0,sizeof(Maze_map_bj));
    queue[base][0]=startx,queue[base][1]=starty,queue[base][2]=0;
    Maze_map_bj[startx][starty]=1;
    while(base!=qtop)
    {
        int x=queue[base][0],y=queue[base][1];
        for(int i=0; i<4; i++)
        {
            if(Maze_map[x+step[i][0]][y+step[i][1]]=='E')
                return 1;
            if(Maze_map[x+step[i][0]][y+step[i][1]]=='.'&&!Maze_map_bj[x+step[i][0]][y+step[i][1]])
            {
                queue[qtop][0]=x+step[i][0],queue[qtop][1]=y+step[i][1];
                queue[qtop][2]=base;
                qtop++;
                Maze_map_bj[x+step[i][0]][y+step[i][1]]=1;
            }
        }
        base++;
    }
    return 0;
}

void Maze::outputBFSmap()
{
    if(!BFS())
    {
        cout<<"maze bu neng zou = = "<<endl;
        return ;
    }
    char newmap[Maze_size][Maze_size];
    for(int i=0; i<length; i++)
        for(int j=0; j<wide; j++)
            newmap[i][j]=Maze_map[i][j];
    while(base!=0)
    {
        newmap[queue[base][0]][queue[base][1]]='*';
        base=queue[base][2];
    }
    cout<<"BFS:"<<endl;
    for(int i=0; i<length; i++)
        for(int j=0; j<wide; j++)
        {
            cout<<newmap[i][j];
            if(j==wide-1)
                cout<<endl;
        }
    cout<<endl;
}
int main()
{
    Maze a;
    a.input();
    a.outputBFSmap();
    a.outputDFSmap();
    return 0;
}


 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
BFS算法模板与练习
BFS算法模板与练习
7 0
力扣429 - N叉树的层序遍历【BFS+DFS】
详细绘图教学和动画制作,附有BFS和DFS的万能模板,来解决二叉树的层序遍历问题
18 0
广度优先搜索(BFS)
广度优先搜索(BFS)
31 0
java实现图的深度优先搜索(DFS)和广度优先搜索(BFS)
深度优先搜索、宽度优先搜索算法属于图算法的一种。
179 0
【数据结构和算法】图的遍历(深度优先遍历DFS与广度优先遍历BFS)
【数据结构和算法】图的遍历(深度优先遍历DFS与广度优先遍历BFS)
46 0
一文搞懂深度优先搜索、广度优先搜索(dfs、bfs)
你问一个人听过哪些算法,那么深度优先搜索(dfs)和宽度优先搜索(bfs)那肯定在其中,很多小老弟学会dfs和bfs就觉得好像懂算法了,无所不能,确实如此,学会dfs和bfs暴力搜索枚举确实利用计算机超强计算大部分都能求的一份解,学会dfs和bfs去暴力杯混分是一个非常不错的选择!
75 0
【31. 走迷宫(BFS)】
## 思路 - 用 `g[n][m] `存储地图,`d[n][m]` 存储起点到 n,m 的距离。 - 从起点开始广度优先遍历地图。 - 当地图遍历完,就求出了起点到各个点的距离,输出`d[n][m]`即可。
72 0
树与图的遍历:DFS,BFS 算法模板
树与图的遍历:DFS,BFS 算法模板
31 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载