自动搬运

查看原文

来自洛谷，原作者为

	Linyijun_ ⎛⎝≥⏝⏝≤⎛⎝

搬运于2025-08-24 23:08:40，当前版本为作者最后更新于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;
}

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