题解

问题分析

本题的目标是加湿器的扩散是通过上下左右四个方向扩展的，我们希望计算在给定最大步数 D 的限制下，所有被加湿器加湿的地板单元格的数量。

解决思路

为了求解此问题，我们可以使用 广度优先搜索（BFS） 来模拟加湿器的扩散过程。

解决方案

  1. 输入解析：
  • 首先读取网格的大小 n 和 m，以及加湿器扩散的最大步数 d。
  • 然后读取网格数据，网格中的元素包括加湿器（H）、地板（.）和墙壁（#）。
  1. BFS 扩散：
  • 初始化一个队列 q，将所有加湿器的位置放入队列中。每个加湿器的初始步数为 0，并标记这些位置为已加湿。
  • 使用 BFS 算法，从所有加湿器出发，逐步扩展到周围的地板单元格。每扩展一步，步数加 1，直到步数达到最大值 d。
  • 扩展时，要确保不跨越墙壁（ # ）并且只扩展到未加湿的地板单元格。
  1. 统计加湿的地板单元格：
  • 在 BFS 完成后，遍历所有单元格，统计已经被加湿的地板单元格数量。

AC Code

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 四个方向的移动：上、下、左、右
int dx[] = {-1, 1, 0, 0};  // 行坐标变化
int dy[] = {0, 0, -1, 1};  // 列坐标变化

// 定义节点结构体，包含位置 (x, y) 和当前的步数 step
struct Node{
	int x, y, step;
};

// 网格的行数、列数和最大扩散步数
int n, m, d;

// 存储网格的二维数组
char a[1010][1010];

// vis 数组记录每个位置是否被加湿
bool vis[1010][1010]; 

// BFS 从多个加湿器出发，加湿周围的地板单元格
void bfs(int n, int m, int d) {
	queue<Node> q;  // 队列存储坐标和步数，存储当前正在扩散的单元格
	
	// 先将所有加湿器的位置加入队列
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'H') {  // 如果该位置是加湿器
				q.push({i, j, 0});  // 将加湿器的位置和初始步数（0）加入队列
				vis[i][j] = true;  // 加湿器自己所在的单元格也会被加湿
			}
		}
	}
	
	// 开始 BFS 扩展
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
		
		// 如果当前步数等于最大步数 d，就不继续扩展
		if (t.step == d) continue;
		
		// 遍历四个方向扩展
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + t.x;  // 计算新的行坐标
			int ny = dy[i] + t.y;  // 计算新的列坐标
			
			// 检查新的坐标是否有效，并且不是墙壁
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == '#') continue;
			
			
			if(!vis[nx][ny]){
				vis[nx][ny] = true;
				q.push({nx, ny, t.step + 1});  // 新位置步数加1
			}
		}
	}
}

int main() {
	// 读取网格的高度、宽度和加湿器扩散的最大步数
	cin >> n >> m >> d;
	
	// 读取网格数据
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	// 使用 BFS 从所有加湿器出发，计算湿润的区域
	bfs(n, m, d);
	
	// 统计被加湿的地板单元格数
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j]) {  // 如果该位置被加湿，答案加1
				ans++;
			}
		}
	}
	
	// 输出湿润的地板单元格数
	cout << ans << endl;
	
	return 0;
}