专栏文章

题解:AT_abc383_c [ABC383C] Humidifier 3

AT_abc383_c题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miquc3az
此快照首次捕获于
2025/12/04 10:52
3 个月前
此快照最后确认于
2025/12/04 10:52
3 个月前
查看原文

题目大意

给你一个 n×mn \times m 的矩阵。# 代表墙壁,. 代表空地,H 代表加湿器。
若一个方格可以由至少一个加湿器 DD 步之内到达,则该方格被视为加湿方格。注意:任何带有加湿器的方格也是加湿方格。
求:加湿方格的个数。

题目分析

有一个很明显的思路,从每一个加湿器一个一个进行 BFS。但显然会超时。其实,我们可以把所有加湿器放进同一个队列里,这样只需要一次 BFS,就求出来加湿方格的个数了。

代码

CPP
#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const int INF = 0x3f3f3f3f;
inline ll read()
{
	ll res = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar();
	while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), putchar(ch); }
const int N = 1e3 + 5;
char ch[N][N];
int n, m, d;
bool check(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; } // 判断这个点有没有出界
int dx[] = {1, -1, 0, 0}; // 方向数组
int dy[] = {0, 0, 1, -1};
bool vis[N][N];
int main()
{
	queue<pi1> q; pi1 tmp;
	n = read(), m = read(), d = read();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> ch[i][j];
			if (ch[i][j] == 'H') // 加湿方格
			{
				tmp = md(md(i, j), 0);
				q.push(tmp);
			}
		}
	while (!q.empty())
	{
		tmp = q.front(); q.pop();
		int x = tmp.ft.ft, y = tmp.ft.sd, step = tmp.sd;
		if (step > d) break;
		vis[x][y] = true; // 标记
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (!check(nx, ny) || ch[nx][ny] == '#' || vis[nx][ny]) continue; // 不合法
			pi1 ttmp = md(md(nx, ny), step + 1);
			q.push(ttmp); // 入队
		}
	}
	int ans = 0; // 统计加湿方格的个数
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ans += vis[i][j];
	write(ans);
	return 0;
}

评论

3 条评论,欢迎与作者交流。

正在加载评论...