BFS模板题——长草

66 阅读 0 评论 44 点赞

我是靠谱客的博主合适鸡，最近开发中收集的这篇文章主要介绍BFS模板题——长草，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

BFS模板题

正文

【问题描述】

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
请告诉小明，k 个月后空地上哪些地方有草。

【输入格式】

输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。

【输出格式】

输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

【样例输入】

4 5
.g…
…
…g…
…
2

【样例输出】

gggg.
gggg.
ggggg
.ggg.

【评测用例规模与约定】

对于 30% 的评测用例，2 <= n, m <= 20。
对于 70% 的评测用例，2 <= n, m <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

注意：

/*
在做算法题时，使用cin和cout在数据量很大时容易造成超时的情况。此时输入输出需要改为使用scanf和printf。下面的代码可节省时间，增强cin和cout的效率。
*/
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

思路

典型的BFS模板题，首先读入整个地图，将种草的点加入到队列，同时标记其已被访问
再从队列中逐个取出，若其month小于k，则对其上下左右进行扩张，并将满足条件的点加入到队列中去，标记已被访问。最后再遍历vis标记数组，输出打印即可

参考题解

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue> 
#include<algorithm>
//标记访问数组
int vis[1010][1010];
//对应（1,0）（0,1）（-1,0）（0，-1）即右上左下
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
//土地
struct point{
	int x;//行 
	int y;//列 
	int month;//第几个月长的 
}; 
using namespace std; 
int main(){
	int n,m,k;
	char ch; 
	queue<point> q;
	//加快cin和cout的效率 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin.tie(0);
	
	cin>>n>>m;
	cin.get(ch);//读取换行符
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin.get(ch);
			if(ch=='g'){//初始化的时候该处有草 
				struct point p={
					i,j,0
				}; 
				q.push(p);
				vis[i][j]=1;//设置该点已被访问 
			}
		}
		cin.get(ch);//读取换行符 
	} 
	cin>>k;
	//bfs通用模板 
	while(!q.empty()){
		struct point p=q.front();
		int month=p.month;
		q.pop();
		if(month<k){//若该块长草的土地的月份小于k，则继续向外扩展 
			for(int i=0;i<4;i++){//循环遍历右上左下四个方向 ，四个新坐标
				int nx=dx[i]+p.x;
				int ny=dy[i]+p.y;
				if(0<=nx&&nx<n&&0<=ny&&ny<=m&&vis[nx][ny]==0){//没有超过边界且未被访问 
					q.push({nx,ny,month+1});//加入队列 
					vis[nx][ny]=1;//设置已被访问 
				}
			}	
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(vis[i][j]==1)cout<<'g';
			else cout<<'.';
		}
		cout<<endl;
	}
	
	return 0;
}