#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;
vector<vector<int>>wet(n+1, vector<int>(m+2));
vector<vector<bool>>check(n+2, vector<bool>(m+2));
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});
}
}for(auto e: sprinkler){
int x=e.first, y=e.second;
check.assign(n+2, vector<bool>(m+2));
queue<pair<int,int>> q;
// wet[x][y]++;
//cout<<x<<" "<<y<<endl;
q.push({x,y});
while(!q.empty()){
auto p=q.front();
q.pop();
if(check[p.first][p.second])continue;
check[p.first][p.second]=true;
wet[p.first][p.second]++;
for(int i=0; i<4; i++){
int xnou=d1[i]+p.first, ynou=d2[i]+p.second;
if(xnou>0 && xnou<=n && ynou>0 && ynou<=m ){
if(!check[xnou][ynou] && max(abs(xnou-x), abs(ynou-y))<=d){
//cout<<xnou<<" "<<ynou<<" "<<max(abs(xnou-x), abs(ynou-y))<<endl;
q.push({xnou, ynou});
}
}
}
}
}int cnt=0;
for(auto e: mush){
//cout<<wet[e.first][e.second]<<endl;
if(wet[e.first][e.second]>=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... |