This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int r, c, d, k, out;
string s;
vector<vector<int>> sum;
vector<pair<int, int>> vp;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> r >> c >> d >> k;
sum.assign(r+5, vector<int>(c+5, 0));// = vector<int>(r+5, vector<int>(c+5));
for (int i=0; i<r; i++) {
cin >> s;
for (int j=0; j<c; j++) {
if (s[j] == 'S') {
int x0=max(0, i+1-d), x1=min(r+1, i+1+d+1), y0=max(0, j+1-d), y1=min(c+1, j+1+d+1);
sum[x0][y0]++;
sum[x0][y1]--;
sum[x1][y0]--;
sum[x1][y1]++;
}
else if (s[j] == 'M') vp.push_back({i, j});
}
}
// for (int i=0; i<=r+1; i++) {for (int j=0; j<=c+1; j++) cout << sum[i][j] << ' '; cout << endl;}
for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1];
for (auto [x, y] : vp) if (sum[x+1][y+1] >= k) out++;
// for (int i=1; i<=r; i++) {for (int j=1; j<=c; j++) cout << sum[i][j] << ' '; cout << endl;}
cout << out;
return 0;
}
/*
5 5 1 1
....M
.M...
..S..
.S...
...M.
1 8 5 2
SM..MM.S
5 5 2 2
....M
.M...
..S..
.S...
...M.
*/
# | 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... |