fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int r,c,D,k;
  4. vector<vector<char> > g;
  5. vector<vector<int> > d;
  6. int cnt(int i, int j)
  7. {
  8. int l = max(1,j-D);
  9. int r = min(c,j+D);
  10. int u = max(1,i-D);
  11. int b = min(r,i+D);
  12. return d[b][r]-d[u-1][r]-d[b][l-1]+d[u-1][l-1];
  13. }
  14. int main()
  15. {
  16. // freopen("MUSHROOM.INP","r",stdin);
  17. // freopen("MUSHROOM.OUT","w",stdout);
  18. cin >> r >> c >> D >> k;
  19. g.resize(r+10);
  20. for(int i=0;i<=r;i++)
  21. g[i].resize(c+10);
  22.  
  23. for(int i=1;i<=r;i++)
  24. for(int j=1;j<=c;j++)
  25. cin >> g[i][j];
  26.  
  27. d.resize(r+10);
  28. for(int i=0;i<=r;i++)
  29. d[i].resize(c+10,0);
  30. for(int i=1;i<=r;i++)
  31. for(int j=1;j<=c;j++)
  32. if(g[i][j]=='S')
  33. d[i][j]=1;
  34. for(int i=1;i<=r;i++)
  35. for(int j=1;j<=c;j++)
  36. d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
  37.  
  38. int res = 0;
  39. for(int i=1;i<=r;i++)
  40. for(int j=1;j<=c;j++)
  41. if(g[i][j]=='M'&& cnt(i,j)>=k)
  42. res++;
  43. cout << res;
  44. }
Success #stdin #stdout 0.01s 5304KB
stdin
5  5  2  2
....M
.M...
..S..
.S...
...M.
stdout
2