恐怖如斯

用户名：1658227145

访问量：901

签　名：

原谅我这一生，不羁放纵爱自由

等　　级
排　　名	4675
经　　验	1592
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

C++迷宫BFS+DP
浏览：190

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

C++迷宫BFS+DP

　　作者: 恐怖如斯　　　　发表时间：2022-04-03 18:56:19 浏览：190　|　评论：0　

原题链接：迷宫问题

# 解题思路
1. 用**dp数组**和**BFS（广度优先搜索）**相结合的方法
2. 先建立一个dp数组，把里面的**初始值都赋为-1，入口地址赋为0**
3. 通过队列，从入口开始，遍历它的上下左右四个方向，相当于向这个四个方向走了一步，
**每一个步的距离=上一个格子的距离+1**
4. 每走一步，就把当前位置加入队列。
5. 重复3，4步，一直不断的循环。
- 如果存在出路，遇到出口位置就退出循环，然后return dp[出口地址];
- 如果不存在出路，因为，开始时，dp全都初始化为-1了，所以当循环完毕，队列为空时，也是return dp[出口地址]，即-1

![思路](/image_editor_upload/20220403064834_50904.png "思路")
# 代码
```cpp
#include<iostream>
#include<queue>
using namespace std;
#define MAX_N 100

char area[MAX_N][MAX_N];	//存放迷宫
int dp[MAX_N][MAX_N];
int n,m;
int Si,Sj,Ei,Ej;    //起点和终点的地址
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};    //走的方向，下、右、上、左

int BFS(){
    queue<pair<int,int>> pre;
    dp[Si][Sj]=0;	//出口距离赋为0
    pre.push(make_pair(Si,Sj));

while(pre.size()){	//队列为空时，退出
        pair<int,int> p=pre.front();pre.pop();
        if(p.first==Ei && p.second==Ej) break;	//该点为出口时，退出
        for(int i=0;i<4;i++){
            int nx=dx[i]+p.first,ny=dy[i]+p.second;
			//该点不能超出范围，不能是墙体，并且要没有走过
            if(nx>=0 && nx<n && ny>=0 && ny<m && dp[nx][ny]==-1 && area[nx][ny]!='#'){
                dp[nx][ny]=dp[p.first][p.second]+1;	//该点距离=上一个点的距离+1
                pre.push(make_pair(nx,ny));	//放入队列
            }
        }
    }
    return dp[Ei][Ej];	//返回出口
}
int main(){
    int k;
    cin>>k;
    while(k){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dp[i][j]=-1;	//给dp数组赋初值为-1
                cin>>area[i][j];
                if(area[i][j]=='S'){	//入口地址
                    Si=i;Sj=j;
                }
                if(area[i][j]=='E'){	//出口地址
                    Ei=i;Ej=j;
                }
            }
        }
        int res=BFS();
        cout<<res<<endl;
        k--;
    }
    return 0;
}
```

0.0分

2 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

恐怖如斯

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

震宇大神的杀毒软件（C语言代码）

C++迷宫BFS+DP

评论区

精彩推荐

不容易系列2 （C语言代码）

小明A+B （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

完数（C语言代码）

幸运数（C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

分糖果（C语言代码）

恐怖如斯

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

震宇大神的杀毒软件 （C语言代码）

C++迷宫BFS+DP

评论区

精彩推荐

不容易系列2 （C语言代码）

小明A+B （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

完数 （C语言代码）

幸运数 （C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

分糖果 （C语言代码）

震宇大神的杀毒软件（C语言代码）

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

完数（C语言代码）

幸运数（C++代码）

分糖果（C语言代码）