SavenNeer

用户名：SavenNeer

访问量：3834

签　名：

等　　级
排　　名	6635
经　　验	1396
参赛次数	1
文章发表	9
年　　龄	0
在职情况	学生
学　　校	山东科技大学
专　　业

　　自我简介：

TA的其他文章

BFS-全域最短路实验
浏览：229

你可能喜欢

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

图论与广度优先搜索基本(个人笔记)

　　作者: SavenNeer　　　　发表时间：2020-01-04 14:38:34 浏览：313　|　评论：0　

###BFS在图论中基础代码-注意点记录
```cpp
#include<algorithm>
#include<iostream>
#include<queue>
#define maxx 52
using namespace std;
typedef struct point
{
    int a;
    int b;
}POINT;
int bfs(int x,int y,int m,int n);
int aim[maxx][maxx];
int num=1;
queue<POINT> q;

int inqueue(int x,int y)
{
    POINT p;
    p.a=x;
    p.b=y;
    q.push(p);
    return 0;
}

int bfs(int x,int y,int m,int n)//核心代码
{
    POINT s;
    if(aim[x][y]!=0)return 0;
    else
    {
        aim[x][y]=num++;
        if(y+1<n&&aim[x][y+1]==0)inqueue(x,y+1);
        if(x>2  &&aim[x-1][y]==0)inqueue(x-1,y);
        if(y>2  &&aim[x][y-1]==0)inqueue(x,y-1);
        if(x+1<m&&aim[x+1][y]==0)inqueue(x+1,y);
//注意，进入队列的元素必须都是有效的才行，这两点条件必须判定
    }
    if(q.empty())return 0;
//递归结束的另一个条件就是队列为空，递归开始前队列就是空的
    s=q.front();
    q.pop();
    x=s.a;
    y=s.b;
    bfs(x,y,m,n);
    return 0;
}

int main()
{
    int m,n;
    cin>>m>>n;
    char ch;
    for(int i=0;i<m;i++)
    {
        for(int k=0;k<n;k++)
        {
            cin>>ch;
            aim[i][k]=(ch=='a')?0:-1;
        }
    }
    //
    bfs(0,0,m,n);
    for(int i=0;i<m;i++)
    {
        cout<<aim[i][0];
        for(int k=1;k<n;k++)
        {
            if(aim[i][k]<10&&aim[i][k]!=-1)cout<<' ';
            cout<<' '<<aim[i][k];
        }
        cout<<endl;
    }
    return 0;
}

```
测试结果如下
```c
input：
    4 10
    acccacccac
    aaaaaaaaac
    acccacccac
    aaacaaaaac
output:
    1 -1 -1 -1  0 -1 -1 -1  0 -1
    2  3  5  7  9 11 13 15 17 -1
    4 -1 -1 -1 12 -1 -1 -1 19 -1
    6  8 10 -1 14 16 18 20 21 -1

Process returned 0 (0x0)   execution time : 5.307 s
    Press any key to continue.
```

0.0分

0 人评分

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

SavenNeer

TA的其他文章

你可能喜欢

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

C二级辅导-同因查找（C语言代码）

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

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

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

图论与广度优先搜索基本(个人笔记)

评论区

精彩推荐

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

Wu-求圆的面积（C++代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

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

printf基础练习2 （C语言代码）

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

C二级辅导-温度转换（C语言代码）

妹子杀手的故事（C语言代码）

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

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

SavenNeer

TA的其他文章

你可能喜欢

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

C二级辅导-同因查找 （C语言代码）

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

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

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

图论与广度优先搜索基本(个人笔记)

评论区

精彩推荐

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

Wu-求圆的面积 （C++代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

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

printf基础练习2 （C语言代码）

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

C二级辅导-温度转换 （C语言代码）

妹子杀手的故事 （C语言代码）

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

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

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

C二级辅导-同因查找（C语言代码）

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

　　评论区

Wu-求圆的面积（C++代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

C二级辅导-温度转换（C语言代码）

妹子杀手的故事（C语言代码）