题解：P11594 [NOISG2018 Finals] Collecting Mushrooms

Linyijun_ · 2025-01-24 09:10:04 · 题解

首先这个题目用暴力去写肯定拿不了满分（会超时）。

对于如何求正解，我们知道洒水器的位置，以及范围，就可以使用二维差分来求解（具体的可参考 P3397 地毯），只不过这个矩形的左下角和右下角需要我们自己去算（还要注意边界）。

这个题目还要注意个令人无语的点，就是数组的设置，建议输完长宽后再建立，再加初始化就行。

下面是我的代码:

#include<bits/stdc++.h>
using namespace std;
int r,c,d,k,ans;
int main(){
    cin>>r>>c>>d>>k;
    int a[r+10][c+10];
    char p[r+10][c+10];
    memset(a,0,sizeof(a));//初始化 
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>p[i][j];
            if(p[i][j]=='S'){
                int x1,y1,x2,y2;
                x1=max(1,i-d);
                x2=min(r,i+d);
                y1=max(1,j-d);
                y2=min(c,j+d);//防超边界 
                a[x1][y1]++;
                a[x1][y2+1]--;
                a[x2+1][y1]--;
                a[x2+1][y2+1]++;//二维差分 
            }
        }
    }for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            if(p[i][j]=='M'&&a[i][j]>=k)ans++;//求答案 
        }
    }cout<<ans;
    return 0;
}

这是本蒟蒻第一次写题解，不喜勿喷。