ZdymU5 - Online C++ Compiler & Debugging Tool

    #include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;   // needed for tree + PBDS

#define pb push_back
#define all(x) x.begin(), x.end()
typedef long long ll;
const ll INF = (ll)1e18;
const ll MOD = 1000000000+7 ;
const double eps = 1e-9 ;
template <class T>
using ordered_set = tree<
    T,
    null_type,
    less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;
int n , m ;
bool valid (int  i , int j) {
    return  i >= 0 && i < n && j  >= 0 && j < m   ;
}
void solve() {

    int   k ; cin >> n >> m >> k ;
    vector < vector< char > > matrix(n , vector < char >(m , '.')) ;
    ll cnt = 0 ;
    for (int  i = 0 ; i <n  ; i ++ ) {
        for (int  j=0 ; j< m ; j ++) {
            cin >> matrix[i][j] ;
            if (matrix[i][j] =='g')cnt ++ ;
        }
    }
    ll mini = n*m;
    vector <  vector < ll  > > prefixgold(n,vector < ll  > (m , 0 ))   ;
    for (int i = 0 ; i< n ; i ++) {
        for (int  j = 0 ; j  <m  ; j ++ ) {
            prefixgold[i][j]  = (matrix[i][j ] == 'g') ;
            if (valid(i , j -1 ) ) prefixgold[i][j] +=prefixgold[i][j-1] ;
            if (valid(i-1 , j  ) ) prefixgold[i][j] +=prefixgold[i-1][j] ;
            if (valid(i-1 , j -1 ) ) prefixgold[i][j] -=prefixgold[i-1][j-1] ;
        }
    }


    for (int i = 0 ; i < n ; i ++ ) {
        for (int j = 0 ; j < m  ; j ++ ) {
            ll loss= 0 ;
            if (matrix[i][j] != '.')continue ;
            int begini= max(0 , i-k+1)  , endi = min (i + k-1 , n -1 ),  beginj= max(0 , j-k+1)  , endj = min (j + k-1 , m -1 );
           loss = prefixgold[endi][endj] ;
            if (valid (begini -1 , endj )) loss-=prefixgold[begini-1][endj] ;
            if (valid (endi , beginj-1 )) loss-=prefixgold[endi][beginj-1] ;
            if (valid (begini-1 , beginj-1 )) loss+=prefixgold[begini-1][beginj-1] ;

          //  cout << i <<" " << j << " " << loss << endl ;
            mini = min( loss , mini ) ;
        }
    }
    cout << cnt- mini << endl ;


}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1 ;  cin >> t;
    int maxi = 200000 + 5;

    while (t--) solve();
    return 0;
}