Submission #1173964

#TimeUsernameProblemLanguageResultExecution timeMemory
1173964CiprianCollecting Mushrooms (NOI18_collectmushrooms)C++20
37 / 100
2095 ms15096 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...