恐怖如斯

用户名：1658227145

访问量：909

签　名：

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

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

　　自我简介：

TA的其他文章

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

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

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

C++迷宫BFS+DP

　　作者: 恐怖如斯　　　　发表时间：2022-04-03 18:56:19 浏览：193　|　评论：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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

恐怖如斯

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

C二级辅导-求偶数和（C++代码）

C语言训练-求函数值（C语言代码）

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

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

C++迷宫BFS+DP

评论区

精彩推荐

求圆的面积（C语言代码）

WU-陶陶摘苹果2 （C++代码）

【金明的预算方案】（C++代码）

用筛法求之N内的素数。（C++代码）

1011题解

1017题解

关于float，double变量的几点说明

蓝桥杯历届试题-翻硬币（C++代码）

分糖果（C语言代码）

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

恐怖如斯

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

C二级辅导-求偶数和 （C++代码）

C语言训练-求函数值 （C语言代码）

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

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

C++迷宫BFS+DP

评论区

精彩推荐

求圆的面积 （C语言代码）

WU-陶陶摘苹果2 （C++代码）

【金明的预算方案】 （C++代码）

用筛法求之N内的素数。 （C++代码）

1011题解

1017题解

关于float，double变量的几点说明

蓝桥杯历届试题-翻硬币 （C++代码）

分糖果 （C语言代码）

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

C二级辅导-求偶数和（C++代码）

C语言训练-求函数值（C语言代码）

　　评论区

求圆的面积（C语言代码）

【金明的预算方案】（C++代码）

用筛法求之N内的素数。（C++代码）

蓝桥杯历届试题-翻硬币（C++代码）

分糖果（C语言代码）