题解：P11594 [NOISG2018 Finals] Collecting Mushrooms

lzx111218 · 2025-01-23 17:58:25 · 题解

P11594 [NOISG2018 Finals] Collecting Mushrooms

题目传送门

思路

给定一个 R \cdot C 的网格，网格中的格子有可能是：

• 蘑菇 M：需要被洒水器浇灌的地方。
• 洒水器 S：能够影响周围格子的格子。
• 空格 .：无需考虑的格子。

• 需要统计所有能够被至少 K 个洒水器浇到的蘑菇。

• 对于每个洒水器，计算它能够影响的区域，并记录每个蘑菇受到多少个洒水器的影响。

• 最终统计有多少蘑菇的影响次数不小于 K。

知道了这些之后呢，我们就可以遍历网格，查找所有蘑菇，并检查其洒水器影响数量是否满足 k，如果满足则认为它是一个好蘑菇，然后 ans 计数即可。

时间和空间复杂度均为 O(RC)。

#include<bits/stdc++.h>
using namespace std;
int r, c, d, k, ans;
char ch; 
int main(){
    char ch;
    scanf("%d%d%d%d", &r, &c, &d, &k);  
    char g[r + 5][c + 5];
    int p[r + 5][c + 5];
    for (int i = 0; i <= r; i++) {
        for (int j = 0; j <= c; j++) {
            p[i][j] = 0;
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            scanf(" %c", &ch); 
            g[i][j] = ch;
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (g[i][j] == 'S') {
                p[max(1, i - d)][max(1, j - d)] += 1;
                p[max(1, i - d)][min(c, j + d) + 1] -= 1;
                p[min(r, i + d) + 1][max(1, j - d)] -= 1;
                p[min(r, i + d) + 1][min(c, j + d) + 1] += 1;
            }
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            p[i][j] = p[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (g[i][j] == 'M' && p[i][j] >= k) {
                ans++;
            }
        }
    }
    printf("%d", ans); 
    return 0;
}