nrs1234

用户名：uq_67668756981

访问量：421

签　名：

小朋友们，代码不会写的话可以来问稽宝哦，不许抄题解~

等　　级
排　　名	7397
经　　验	1261
参赛次数	0
文章发表	2
年　　龄	16
在职情况	学生
学　　校	滑稽粉丝团
专　　业	睡觉

　　自我简介：

我们稽宝真的是太强啦！

TA的其他文章

BFS板子题（C++版）
浏览：151

你可能喜欢

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

BFS板子题（C++版）

　　作者: nrs1234　　　　发表时间：2023-10-29 16:28:02 浏览：151　|　评论：0　

原题链接：信息学奥赛一本通T1252-走迷宫

# 分析题意
这道题是一道BFS的板子题，属于是在网格中寻找最短路。在求解无边权最短路问题时，我们一般都可以采用BFS来做。
# BFS
BFS简而言之，就是优先考虑离当前节点最近的所有点，再依次递推。比如说本题的样例：

5 5
    ..###
    #....
    #.#.#
    #.#.#
    #.#..
这张图我们的遍历顺序是这样的：

12###
    #3456
    #4#6#
    #5#7#
    #6#89

#### （以上对DFS的理解思路来源：ACwing大雪菜 yxc）
点上的数字就是它们被遍历的顺序，已经被遍历过（已经有数字）的点不会被再次遍历。这样我们就求出了每个点从起点出发的最短路。

最后根据题意，只需要输出右下方的点的数字，即（r，c）就可以了。
# 代码编写
在BFS中，我们需要一个队列（queue）来存储符合规定，准备被遍历的点。

因为点是二维的，再建立队列时，需要用一个pair来表示该点的x,y坐标。

每次循环时取队头（较先入队的点），再判断该点周围是否有可以走到的点。如果又可以走到的点，就让该点入队，等待遍历。如果队列空了,即没有可以遍历的点了，那么所有的点已经被走完了。这时循环停止，直接输出所求点步数。

代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;//定义pair的符号
const int N=45;
bool st[N][N];//用来记录当前点是否被遍历过
char g[N][N];//存储输入进来的图
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},dist[N][N];//上下左右单位向量，以及记录起点与每一个点的距离
int main(){
    int r,c;
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++) scanf("%s",g[i]+1);
    queue<PII> q;//创建队列
    q.push({1,1});//起点入队
    st[1][1]=true;//记录起点已被遍历，防止有2号点遍历回起点
    dist[1][1]=1;//根据题意，起点也算一步，所以起点步数为1
    while(q.size()){//判断是否有能走的点
        auto t=q.front();//取当前点
        q.pop();//弹出取走的点
        for(int i=0;i<4;i++){//遍历该点上下左右四个点，看能不能走
            int x=t.first+dx[i],y=t.second+dy[i];//记录下一点坐标
            if(x>0&&x<=r&&y>0&&y<=c&&!st[x][y]&&g[x][y]=='.'){//判断下一点是否出界，是否已被遍历，是否是墙
                q.push({x,y});//符合规定，将点入队
                st[x][y]=true;//已被遍历
                dist[x][y]=dist[t.first][t.second]+1;//更新该点所需步数
            }
        }
    }
    printf("%d",dist[r][c]);//输出答案
    return 0;
}
```

0.0分

3 人评分

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

编程语言转换

万能编程问答

代码解释器

nrs1234

TA的其他文章

你可能喜欢

C二级辅导-统计字符（C语言代码）

C二级辅导-阶乘数列（C语言代码）

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

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

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

BFS板子题（C++版）

评论区

精彩推荐

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

母牛的故事（C语言代码）

校门外的树（C语言代码）

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

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

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

这可能是一个假的冒泡法

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

蛇行矩阵（C语言代码）

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

nrs1234

TA的其他文章

你可能喜欢

C二级辅导-统计字符 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

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

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

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

BFS板子题（C++版）

评论区

精彩推荐

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

母牛的故事 （C语言代码）

校门外的树 （C语言代码）

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

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

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

这可能是一个假的冒泡法

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

蛇行矩阵 （C语言代码）

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

C二级辅导-统计字符（C语言代码）

C二级辅导-阶乘数列（C语言代码）

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

　　评论区

母牛的故事（C语言代码）

校门外的树（C语言代码）

蛇行矩阵（C语言代码）