耿祥瑞

用户名：dotcpp0692230

访问量：924

签　名：

等　　级
排　　名	561
经　　验	4357
参赛次数	0
文章发表	12
年　　龄	0
在职情况	学生
学　　校	齐鲁理工学院
专　　业	数据科学与大数据技术

　　自我简介：

TA的其他文章

发工资咯（一往直前！贪心法）
浏览：84

你可能喜欢

走迷宫—BFS广度优先搜索

　　作者: 耿祥瑞　　　　发表时间：2023-10-14 12:58:57 浏览：65　|　评论：0　

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

定义char g[][]为迷宫，把n行m列的迷宫输入进去，通过bfs广度优先搜索来找到从（1，1）到（n。m）的最短路径，在定义数组的时候是从（0，0）开始的所以要找到（0，0）到（n-1，m-1）的最短路径。
d[x][y]表示 （x,y）这个位置到起点需要走的距离
q[]表示走的哪个位置
BFS模板：
1.定义一个队列
2.起始元素入队，找到邻接的符合条件的下一个位置（条件因题目而异），这里的条件就是 在迷宫里面的上下左右四个方向移动不能越出迷宫边界并且此位置为'.' 并且此位置没走过
3.把队头元素给t，对头元素出队，找到符合条件的位置后插入到队列里面，并修改此位置到起始位置的距离为上一个元素到起始位置的距离加一，直到队列里面没有元素说明查找结束。
4.最后输出最后一个位置即（n-1，m-1）到起始位置的距离 就是最短距离。
最后输出的时候要加一 因为题目说起始位置也算走了一步。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 500;
int n,m;
char g[N][N];
int d[N][N];
PII q[N*N];

int bfs()
{
    int tt = 0, hh = 0;
    memset(d,-1,sizeof d);
    d[0][0] = 0;
    q[0] = {0,0};
    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};
    while(hh <= tt){
        auto t = q[hh++];
        for(int i = 0 ;i < 4;i++){
           int x = t.first + dx[i] , y = t.second + dy[i];
           if(x >=0 && x < n && y >=0 && y < m && g[x][y]=='.' && d[x][y]==-1){
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }
    return d[n-1][m-1] + 1;
}

int main()
{
    cin >> n >> m;
    for(int i = 0 ;i < n;i++){
        for(int j = 0 ;j < m;j++){
            cin >> g[i][j];
        }
    }
    cout <<  bfs();
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

耿祥瑞

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并（C语言代码）

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

IP判断（C++代码）

C语言训练-排序问题<2> （C++代码）（sort函数）

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

走迷宫—BFS广度优先搜索

评论区

精彩推荐

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

字符串比较（C语言代码）答案错误？？？？

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

打印十字图（C语言代码）

蚂蚁感冒（C语言代码）

1126题解

图形输出（C语言代码）

DNA （C语言代码）

耿祥瑞

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并 （C语言代码）

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

IP判断 （C++代码）

C语言训练-排序问题<2> （C++代码）（sort函数）

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

走迷宫—BFS广度优先搜索

评论区

精彩推荐

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

字符串比较 （C语言代码）答案错误？？？？

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

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

打印十字图 （C语言代码）

蚂蚁感冒 （C语言代码）

1126题解

图形输出 （C语言代码）

DNA （C语言代码）

数据结构-有序线性表的有序合并（C语言代码）

IP判断（C++代码）

　　评论区

字符串比较（C语言代码）答案错误？？？？

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

打印十字图（C语言代码）

蚂蚁感冒（C语言代码）

图形输出（C语言代码）