#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <immintrin.h> #ifndef DEBUG //#pragma GCC optimize("O3") //#pragma GCC target("avx2") #endif using namespace __gnu_pbds; using namespace __gnu_cxx; using namespace std; // using ld = long double; using ll = long long; using i128 = __int128; using ull = unsigned long long; using pll = std::pair<ll, ll>; using cmpl = std::complex<ld>; template<typename T> using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>; constexpr ll MOD1 = 998244353; constexpr ll MOD = 1000000007; constexpr ll INV2 = 499122177; constexpr ld PI = 3.141592653589793; const ld eps = 1e-7; const ll K = 500; //const ll C = 200; std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count()); ld START_TIME = clock(); struct Fenwick{ std::vector<std::vector<ll>> f; Fenwick(ll n, ll m){ f.resize(n + 1, std::vector<ll>(m + 1)); } void add(ll i, ll j){ ++i, ++j; while (i < f.size()){ ll j1 = j; while (j1 < f[i].size()){ ++f[i][j1]; j1 += j1 & -j1; } i += i & -i; } } ll get(ll x, ll y){ ll ans = 0; while (x > 0){ ll j = y; while (j > 0){ ans += f[x][j]; j -= j & -j; } x -= x & -x; } return ans; } ll get(ll x, ll y, ll x1, ll y1){ ll ddv = get(x1, y1) + get(x, y); return ddv - get(x1, y) - get(x, y1); } }; void solve() { ll n, m, d, k; std::cin >> n >> m >> d >> k; std::vector<std::string> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } Fenwick f(n, m); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 'S'){ f.add(i, j); } } } ll ans = 0; for (ll i = 0; i < n; ++i) { for (ll j = 0; j < m; ++j) { if (a[i][j] == 'M'){ ll cnt = f.get(std::max(0ll, i - d), std::max(0ll, j - d), std::min(i + d + 1, n), std::min(j + d + 1, m)); ans += cnt >= k; } } } std::cout << ans; } signed main() { #ifdef DEBUG std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin); #else // std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout); #endif std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false); int tt = 1; // ll g; std::cin >> g; // std::cin >> tt; while (tt--) { solve(); } #ifdef DEBUG std::cerr << '\n'; ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC; std::cerr << "Time: " << TIME << '\n'; #endif }