首页 > 其他分享 >蓝桥杯-长草(BFS)

蓝桥杯-长草(BFS)

时间:2024-04-11 20:55:05浏览次数:21  
标签:BFS int len 蓝桥 flag 长草 空地 节点

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

相关文章

  • P8725 [蓝桥杯 2020 省 AB3] 画中漂流
    题目:链接:https://www.luogu.com.cn/problem/P8725思路:dp[i][j]表示第i个时刻还有多少体力之前的错误思路:dp[i][j][k]表示第i个时刻,在j位置,有k个体力。但是注意:这三个变量并不是相互独立!!动规的一个取变量原则应该是相互独立确定某个状态。剩下k体力和i时刻可以推出位置!!site......
  • 蓝桥杯2016国赛-路径之谜
    0.题目小明冒充X星球的骑士,进入了一个奇怪的城堡。城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是nxn个方格。【如图1.png】所示。按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一......
  • 蓝桥杯训练
    P8712[蓝桥杯2020省B1]整数拼接-洛谷|计算机科学教育新生态(luogu.com.cn)题解:这道题和牛客类似,我们换一个思路我们可以开一个二维数组  一位用来记录拼在后面数的长度,一个用来记录这个数乘上10的(后面数的长度)模10我们直接乘1到10,全部记录下来然后枚举右边的数,看......
  • 太阳(蓝桥杯14届)
    https://www.lanqiao.cn/problems/3529/learning/?subject_code=2&group_code=5&match_num=14&match_flow=1&origin=cup1importjava.util.*;2//1:无需package3//2:类名必须Main,不可修改4importjava.util.Map.Entry;56publicclassDemo1{7......
  • 第十二届蓝桥杯省赛真题(C/C++大学B组)
    目录#A空间#B卡片#C直线#D货物摆放#E路径#F时间显示#G砝码称重#H 杨辉三角形#I双向排序#J括号序列#A空间#include<bits/stdc++.h>usingnamespacestd;intmain(){ cout<<256*1024*1024/4<<endl; return0;}#B卡片#include<bit......
  • 2024SMU蓝桥训练2补题
    C-密文搜索思路:不难。voidsolve(){//C--密文搜索可以不是字符串哈希--因为只需要知道相同长度字符串对字母出现情况,可以对字符串进行!!!排序!!!stringstr;cin>>str;intn,ans=0;cin>>n;unordered_map<string,int>mp;for(inti=1;i<=n;i++){......
  • P8791 [蓝桥杯 2022 国 AC] 内存空间 题解
    题面一道比较简单模拟题,但是要分类讨论一.读完题你应该知道的1.输入一共有T+1行,输入含有空格。(处理1)2.对于每一行变量定义的语句,只会出现一种变量类型,type只可能是int或long,只有一个分号。(处理1,处理2)3.统计内存过程中用B做单位,保证一定有输出,但在输出时要换......
  • P8779 [蓝桥杯 2022 省 A] 推导部分和
    并查集板子题#include<bits/stdc++.h>#defineR(x)x=read()#defineRLL(x)x=readLL()usingnamespacestd;typedeflonglongLL;constintN=1e5+5;inlineintread(){intx=0,f=1;charch=getchar();while(ch<'0'|......
  • 蓝桥杯单片机基于西风模板超声波底层
    超声波是外设需要重新自己编写c文件和h文件在c文件中需要编写两个函数一个是波的初始化一个是方波的读取voidWave_Init(){unsignedchari;for(i=0;i<8;i++){TX=1;发送信号Delay(12)us哦Tx=0在延时12us}这样波的初始化就好了}unsignedcharWave_Read(){unsig......
  • 蓝桥杯STM32G431RBT6-各个外设的配置过程
    LED,按键配置LED点亮,按键采集按键值前期准备:通过Cubemx生成一个源文件方便后续直接使用。  源文件准备完毕以后开始进行按键和LED的配置LED对比芯片引脚连接图可以知道8个LED分别连接在GPIOC的如下8个引脚中      Cubemx中......