0.题目
【问题描述】
小明有一块空地,他将这块空地划分为 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..
.....
【样例输出】:
gggg.
gggg.
ggggg
.ggg.
1. 题解
1.1 BFS搜索
思路
思路和DFS是有一点像的,主要考虑结束条件(check(这里直接写在BFS代码里)), 边界条件(dp函数), BFS使用的队列
1.结束条件: 队列为空且k(月份)==0; 前者代表所有层数均已完成了BFS扩展, 后者代表已完成BFS层数k
2.边界条件: 这里注意不要被传统的x,y轴给局限了, 你要看数组的下标位置对应,
比如像我们使用flag[x][y], 我们要看开始赋值的时候, 外层循环为 i= 1->n, 内层循环为 j = 1->m; 即1<=x<=n, 1<=y<=m
3.BFS编写:
3.1 首先进行初始化,将开始所有种草的节点(值为'g')的节点进行标记(flag(这里其实不需要用flag,自己的值均为'g'就是一种标记)), 且存入队列,便于后面进行BFS扩展
3.2 记录本层总节点数len, 取队列首节点,开始向四周进行BFS扩展,并将新节点存入队列(对于重复点不需要存入队列!!!); 当len归零时,标志本层节点BFS扩展完毕,开始扩展下一层节点,更新len=p.size(){下一层节点数},总层数k--;
3.3 最后输出更新过的所有节点即可.
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n, m;
int len; // 表示当前层总数量
int k; // 表示总次数(月份)
queue<pair<int, int>> q; // BFS实现队列
char nodes[1005][1005];
bool flag[1005][1005] = {false};
// 图论常用移动数组
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
// 边界检测
bool pd(int x, int y) {
// 超出边界
if(x < 1 || x > n || y < 1 || y > m) {
return false;
}
// 重复选取
if(flag[x][y]) {
return false;
}
return true;
}
void BFS() {
while (!q.empty() && k > 0) {
// 取当前层的一个节点
pair<int, int> node = q.front();
int x = node.first;
int y = node.second;
q.pop();
// 开始移动
for(int i = 0; i < 4; i++) {
int xt = x + dx[i];
int yt = y + dy[i];
if(!pd(xt, yt)) {
continue;
}
// 通过检测 (更新数据(flag,node,q),进行本层下一次的BFS)
if(!flag[xt][yt]) {
flag[xt][yt] = true;
nodes[xt][yt] = 'g'; // 更新节点状态
q.push(make_pair(xt, yt));
}
}
// 经过四个方向的移动后,更新数据,该层节点数-1; 如果len==0,说明本层节点遍历完毕(进入下一层节点,即下一个月)
len--;
if (len == 0) {
len = q.size();
k--;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> nodes[i][j];
if(nodes[i][j] == 'g') {
pair<int, int> tempNode = make_pair(i, j);
flag[i][j] = true;
q.push(tempNode);
}
}
}
cin >> k;
len = q.size();
BFS();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cout << nodes[i][j];
}
cout << endl;
}
return 0;
}
标签:BFS,int,len,蓝桥,flag,长草,空地,节点
From: https://www.cnblogs.com/trmbh12/p/18130014