#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll r, c, d, k;
cin >> r >> c >> d >> k;
ll realr = r;
ll realc = c;
if (r > c) {
std::swap(r, c);
}
set<pair<ll, ll>> s, m;
vector<vector<char>> adj(r, vector<char>(c));
vector<vector<ll>> count(r, vector<ll>(c + 1)), pref(r, vector<ll>(c + 1));
if (realr != r) {
for (int i = 0; i < realr; i++) {
for (int j = 0; j < realc; j++) {
cin >> adj[j][i];
if (adj[j][i] == 'S') {
s.insert({j, i});
}
if (adj[j][i] == 'M') {
m.insert({j, i});
}
}
}
} else {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> adj[i][j];
if (adj[i][j] == 'S') {
s.insert({i, j});
}
if (adj[i][j] == 'M') {
m.insert({i, j});
}
}
}
}
for (auto [x, y] : s) {
ll topl = max(0LL, y - d);
ll topr = min((c - 1), y + d);
ll downl = max(0LL, x - d);
ll downr = min((r - 1), x + d);
for (int i = downl; i <= downr; i++) {
count[i][topl]++;
count[i][topr + 1]--;
}
}
for (int i = 0; i < r; i++) {
pref[i][0] = count[i][0];
for (int j = 1; j < c; j++) {
pref[i][j] = pref[i][j - 1] + count[i][j];
}
}
ll ans = 0;
for (auto [x, y] : m) {
if (pref[x][y] >= k) {
ans++;
}
}
cout << ans << "\n";
}
| # | 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... |