题解 9 Divisors

xyx4042024-12-072024-12-09

思路：

多源 bfs。

把每一个加湿器看做一个起点，求他们走 $D$ 步最多可以走到几个格子。

对每一个加湿器的坐标进行 bfs。

bfs 模版里的标记数组要修改成 int 类型，并且标记的是到达这个位置的最小步数。
如果到达这个点时的步数小于标记的步数，才可以继续往下搜，因为只有还可以走的步数大于原本可以走的步数，才有可能走到更多的点，否则走到的点只会是走过的点。
其余的就是模版了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
char s[1100][1100];
int H,W,D;
int bj[1100][1100];
struct node{
	int x,y,step;
};
void bfs(int x,int y){
	queue<node>dl;
	dl.push({x,y,0});
	while(dl.empty()==0){
		node tamp=dl.front();dl.pop();
		int step=tamp.step;
		if(bj[tamp.x][tamp.y]<=step)continue;
		bj[tamp.x][tamp.y]=step;
		if(tamp.step==D){
			continue;
		}
		if(s[tamp.x][tamp.y+1]=='.'){
			dl.push({tamp.x,tamp.y+1,step+1});
		}
		if(s[tamp.x][tamp.y-1]=='.'){
			dl.push({tamp.x,tamp.y-1,step+1});
		}
		if(s[tamp.x+1][tamp.y]=='.'){
			dl.push({tamp.x+1,tamp.y,step+1});
		}
		if(s[tamp.x-1][tamp.y]=='.'){
			dl.push({tamp.x-1,tamp.y,step+1});
		}
	}
}
int main(){
	cin>>H>>W>>D;
	memset(bj,100,sizeof(bj));
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++)cin>>s[i][j];
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(s[i][j]=='H'){
				s[i][j]='.';
				bfs(i,j);
			}
		}
	}
	int an=0;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(bj[i][j]!=1684300900)an++;
		}
	}
	cout<<an;
	return 0;
}