蓝桥杯真题长草，BFS解_长草 蓝桥

题目链接：https://www.lanqiao.cn/problems/149/learning/
题目描述：

解题思路：
用BFS，首先将有草的点入队列（push），然后用队列的长度当循环结束条件，取出队头（front），然后删除（pop），然后将队头符合条件的上下左右入队列（长过的不用长，p月长不到的也不用入队），当队列为空时就长完了。

代码如下

#include<bits/stdc++.h>
using namespace std;
int pp[1005][1005];
struct node{
    int x,y;
};
queue<node>q;
char a[1005][1005];
int fx[4][4]={{0,1},{1,0},{-1,0},{0,-1}};//方向
int main()
{
    int n,m,p;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='g'){
                q.push({i,j});//把有草的空地入队列
                pp[i][j]=0;
            }
        }
    }
    cin>>p;
    while(q.size()){
        node k=q.front();//取出队头
        q.pop();
        for(int i=0;i<4;i++){
            int x=k.x+fx[i][0];//四个方向
            int y=k.y+fx[i][1];
            if(x<1||y<1||x>n||y>m||a[x][y]=='g'||pp[k.x][k.y]>=p) continue;//越界的情况和长完p个月的就不用入队列了
            pp[x][y]=pp[k.x][k.y]+1;//
            q.push({x,y});//入队列，下个月长它的上下左右
            a[x][y]='g';//长草
        }
    }
     for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
           cout<<a[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