题解：AT_abc383_c [ABC383C] Humidifier 3

· · 题解

题目大意

给你一个 n \times m 的矩阵。# 代表墙壁，. 代表空地，H 代表加湿器。

若一个方格可以由至少一个加湿器 D 步之内到达，则该方格被视为加湿方格。注意：任何带有加湿器的方格也是加湿方格。

求：加湿方格的个数。

题目分析

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

代码

#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;
}