道尽似空

用户名：dengmouren

访问量：3900

签　名：

等　　级
排　　名	11351
经　　验	1035
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校	重庆邮电大学
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1252-走迷宫-题解（C++代码）看我这一个就学会bfs最基础的了
浏览：1250

你可能喜欢

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

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

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

信息学奥赛一本通T1252-走迷宫-题解（C++代码）看我这一个就学会bfs最基础的了

　　作者: 道尽似空　　　　发表时间：2020-09-10 19:57:29 浏览：1250　|　评论：0　

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

这是最基本的bfs搜索题目，使用队列，开始把第一个也就是起点放进去，然后使用for循环遍历这个点的周围的四个位置，若是符合条件（没有越界，没有被访问过，可以走）就再次放在队列里面，等待下一次pop出来，非常简单，用来练手再好不过了，建议本题不会做的，多分析现成代码，想清楚过程，然后过一天再想想，重新码一遍。
```cpp
#include<iostream>
#include <queue>
using namespace std;
int judge[41][41]={0};//标记地图
char a[41][41];//地图
int r,c;
struct node{
    int x;
    int y;
    int step;
    node(int xx,int yy,int stepp){
        x=xx;
        y=yy;
        step=stepp;
    }
};//便于存储，可以直接node a（0，0，0）初始化，即a.x=0。。。。。	
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//改变方向
queue<node> q;//设置队列
bool check(int x,int y){//判断是否符合条件
    if(x<0||x>=r||y<0||y>=c||judge[x][y]||a[x][y]=='#'){
        return false;
    }
    return true;
};
int bfs(node start){
    node next(0,0,0),cur(0,0,0);
    while(!q.empty()){//如果q空还没有找到，那就是找不到了
        cur=q.front();
        q.pop();
        if(cur.x==r-1&&cur.y==c-1){//终止条件，即找到终点了
            return cur.step+1;
        }
        for(int i=0;i<4;i++){
            next.x=cur.x+dir[i][0];//横坐标变换
            next.y=cur.y+dir[i][1];//纵坐标变换
            next.step=cur.step+1;//每次遍历周围的一个点，就走一步，如果不符合下面if里面的条件，此时的next也不会被push进q里面，相当于回溯
            if(check(next.x, next.y)){
                q.push(next);
                judge[next.x][next.y]=1;//标记已走过
            }
        }
    }
    
    return -1;
}
int main(){
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>a[i][j];
        }
    }
    node start(0,0,0);
    q.push(start);
    judge[0][0]=1;
    cout<<bfs(start)<<endl;
    return 0;
}

```

0.0分

45 人评分

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

道尽似空

TA的其他文章

你可能喜欢

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

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

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

矩形面积交（Java代码）

【明明的随机数】（C++代码）

信息学奥赛一本通T1252-走迷宫-题解（C++代码）看我这一个就学会bfs最基础的了

评论区

精彩推荐

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

【出圈】（C语言代码）

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

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

字符逆序（C语言代码）

1118（求助_已解决）

IP判断（C语言代码）

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

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

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

道尽似空

TA的其他文章

你可能喜欢

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

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

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

矩形面积交 （Java代码）

【明明的随机数】 （C++代码）

信息学奥赛一本通T1252-走迷宫-题解（C++代码）看我这一个就学会bfs最基础的了

评论区

精彩推荐

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

【出圈】 （C语言代码）

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

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

字符逆序 （C语言代码）

1118（求助_已解决）

IP判断 （C语言代码）

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

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

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

矩形面积交（Java代码）

【明明的随机数】（C++代码）

　　评论区

【出圈】（C语言代码）

字符逆序（C语言代码）

IP判断（C语言代码）