蓝桥杯广度优先搜索|最短路径问题|长草问题(C++)_蓝桥杯长草c++

广度优先搜索

BFS，其英文全称是 Breadth First Search，意为广度优先搜索，是所有的搜索手段之一。它是从某个状态开始，将所有节点加入一个先进先出的队列，然后一层一层进行状态转移，并且展开节点。

广度优先搜索基本概念

作为搜索算法的一种，BFS 相较于 DFS 而言，BFS 是一层一层展开的，那么对于有多个终态时，最先找到的一定是最短的。

广度优先搜索算法的设计步骤

按照定义设计：

1. 确定该题目的状态（包括边界）
2. 找到状态转移方式
3. 找到问题的出口，计数或者某个状态
4. 设计搜索
   会发现我们前期要找到的参数基本一致，所以在一般情况下 BFS 和 DFS 可以相互转换。
   伪代码：

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
bool pd(参数){
    相应操作
}
void bfs()
{
    1. 把根节点放入队列尾端
    2. 每次从队列中取出一个节点
    3. Check 判断是不是答案，如果是结束算法 return;
    4. 把当前取出的节点扩展，如果扩展后的节点经Pd()后符合要求，就放入队列，不符合就不放。
    5. 转到步骤2，循环执行
}

如果所有节点被扩展完了，没有找到答案就无解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

BFS原理

BFS搜索的原理：逐层扩散，从起点出发，按层次从近到远，逐层先后搜索
编码：用队列实现
应用：BFS一般用于求最短路径问题，BFS的特点是逐层搜索，先搜到的层离起点更近

BFS：找最短路径

找从@到*最短路径

最短路径问题用BFS

BFS的特点：逐层扩散

• 往BFS的队列中加入邻居结点时，按距离起点远近的顺序加入，先加入距离起点为1的邻居结点，加完之后，再加入距离为2的邻居结点，等等
• 搜完一层，才会继续搜下一层
  最短路径：从起点开始，沿着每一层逐步往外走，每多一层，路径长度就增加1。
  所有长度相同的最短路径都是从相同的层次扩散出去的
  搜到第一个到达终点的路径，就是最短路径

长草

题目链接
难度: 简单
标签: 模拟, BFS, 2020, 省模拟赛
题目描述:
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
输入描述:
输入的第一行包含两个整数 n,m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。 其中，2≤n,m≤1000，1≤k≤1000
输出描述:
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
输入输出样例:
示例:
输入:

4 5
.g...
.....
..g..
.....
2
1
2
3
4
5
6

输出:

gggg.
gggg.
ggggg
.ggg.
1
2
3
4

运行限制:

    最大运行时间：1s
    最大运行内存: 256M
1
2

解题思路:
这个题目简直就是为了广度优先搜索设置模板题，由于这个题目是输出广度优先搜索 K 次扩展后的终态，那我们就不用设置判断函数。
这里用一个 N×M 的矩阵来表示草地。

1. 算法开始：
   将字母为 g 的草地的位置加入队列，然后向下执行
2. 判断边界：
   判断是否已经长了草，判断是否超出边界范围
3. 搜索过程：
   不断从队列取出一个节点，进行上下左右的扩展，执行 2 判断边界，符合就放入队列，不符合就跳过。
   执行 K 次扩展，输出草地状态。
4. check(参数)：
   这里不需要进行 Check，判断符不符合题意，有没有剪枝…

C++ 语言描述:

#include <bits/stdc++.h>
using namespace std;

const int M = 1005;

struct PII
{
    int first;
    int second;
};
// C++ 有个数据类型叫 pair 上面的就可以定义为 pair<int,int> 用起来比较方便。

PII tempPair;//临时结点
char Map[M][M];
//---------图的路径搜索常用方向移动表示-------
int dx[4]= {0,1,-1,0};
int dy[4]= {1,0,0,-1};
// 两两组合形成上下左右四个方向
//      1------------------> x
//      |
//      |
//      |
//      |
//      |
//      |
//      |
//      ↓
//      y

// dx[0]=0 dy[0]=1 那么代表向下的方向

// dx[1]=1 dy[1]=0 那么代表向右的方向

// dx[2]=-1 dy[2]=0 那么代表向左的方向

// dx[3]=0 dy[3]=-1 那么代表向上的方向

int n;// n 行
int m;// m 列
int k;// k 次

queue<PII > q; //广度优先搜索所用的队列

int len;//记录节点数量方便后续k的计算
bool pd(int x, int y)
{
    if(x<1)
        return 0;
    // /x 轴坐标 左侧越界
    else if(x>n)
        return 0;
    //x 轴坐标 右侧越界
    else  if(y<1)
        return 0;
    //y 轴坐标 上侧越界
    else if(y>m)
        return 0;
    //y 轴坐标 下侧越界
    else if(Map[x][y]=='g')
        return 0;
    //已经长草了
    else return 1;
    // 在范围内，且没长草
}

void BFS()
{
    //BFS
    while(!q.empty()&&k>0)
    {
        tempPair = q.front();
        q.pop();
        //这两步是取出队首的节点

        int x = tempPair.first;//横坐标
        int y = tempPair.second;//纵坐标

        for(int i=0; i<4; i++)
        {
            int nowx = x+dx[i]; //扩展后的横坐标
            int nowy = y+dy[i]; //扩展后的纵坐标

            if(pd(nowx,nowy))
            {
                q.push({nowx,nowy});
                Map[nowx][nowy]='g';
            }
            //符合要求执行扩展，不符合要求，忽略即可。
        }

        len--; //每取出一个节点len  -1
        if(len==0)
        {
            //当len =0 时，代表当前层扩展完了，那么就代表第一个月扩展完了
            k--; // 所以k--
            len = q.size(); // 当前层扩展完了，那就该扩展下一层了，所以len又被赋值为下一层的节点数目的值
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>Map[i][j];
            if(Map[i][j]=='g')
            {
                tempPair.first=i;
                tempPair.second=j;
               // cout<<i<<""<<j<<endl;
                q.push(tempPair);//将初始有树的结点加入队列
            }
        }
    }

    len = q.size();//记录第一层的节点数量方便后续k的计算
    cin>>k;
    BFS();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cout<<Map[i][j];
        }

        cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132