#include <bits/stdc++.h>
using namespace std;
#define int long long
int d1[4]={0,0,1,-1};
int d2[4]={1,-1,0,0};
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,d,k;
cin>>n>>m>>d>>k;
map<pair<int,int>, int>wet;
vector<pair<int,int>>sprinkler, mush;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
char x;
cin>>x;
if(x=='S')sprinkler.push_back({i,j});
if(x=='M')mush.push_back({i,j});
}
}if(n==1){
vector<pair<int,int>>intervals;
for(auto e:sprinkler){
intervals.push_back({max(e.first-d, 1LL), min(e.second+d, m)});
}sort(intervals.begin(), intervals.end());
int cnt=0;
vector<int>p(m+2), pref(m+2);
for(auto e: intervals){
p[e.first]++;
p[e.second]--;
}for(int i=1; i<=m; i++){
pref[i]=pref[i-1]+p[i];
}for(auto e: mush){
if(pref[e.second]>=k)cnt++;
}cout<<cnt<<endl;
}else {
for(auto e: mush){
for(auto f: sprinkler){
if(max(abs(e.first-f.first), abs(e.second-f.second))<=d){
wet[e]++;
}
}
}
int cnt=0;
for(auto e: mush){
//cout<<wet[e.first][e.second]<<endl;
if(wet[e]>=k)cnt++;
}cout<<cnt<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |