In the following, we try to solve the following problem in \(O(W)\) time: we have a grid with \(1\) row and \(W\) columns. Is it possible to have \(K\) consecutive os horizontally within the grid? If possible, at least how many operations are required? (The original problem can be broken down to such problem for each column and row, which can be done in a total of \(O(HW)\) time.)

Given consecutive \(K\) squares \((1, i), (1, i+1), \ldots, (1, i+K-1)\) in this grid (which we simply refer to by segment \([i, i+K-1]\)), they can be filled with o if and only if the segment \([i, i+K-1]\) does not contain x. In such case, the minimum number of operations required to fill the segment \([i, i+K-1]\) with o equals the number of . in the segment.

Therefore, one can find the answer if one can find the numbers of x and . within each of \((W-K+1)\) segments \([1, K], [2, K+1], \ldots\), and \([W-K+1, W]\). This can be found fast as cumulative sums of the numbers of x and ..

Specifically, for each \(i = 0, 1, 2, \ldots, W\), let \(X_i\) and \(D_i\) be the number of x and ., respectively, in the segment \([1, i]\); by precalculating \(X_i\) and \(D_i\), the number of x and . in each segment \([i, i+K-1]\) can be found as \(X_{i+K-1} - X_{i-1}\) and \(D_{i+K-1} - D_{i-1}\), respectively, which can be evaluated in \(O(1)\) time each. This way, the values for \((W-K+1)\) segments \([1, K], [2, K+1], \ldots, [W-K+1, W]\) can be found in a total of \(O(W)\) time.

The following is sample code in C++ language for this problem.

#include <iostream>
using namespace std;

int H, W, K;
string S[200001];
int X[200001], D[200001];

int main(void){
  cin >> H >> W >> K;
  for(int i = 1; i <= H; i++) cin >> S[i];
  for(int i = 1; i <= H; i++) S[i] = "#" + S[i]; // This is just for having the same index in the code and editorial

  int ans = 1e9;
  for(int y = 1; y <= H; y++){
    for(int i = 1; i <= W; i++){
      X[i] = X[i-1], D[i] = D[i-1];
      if(S[y][i] == 'x') X[i]++;
      if(S[y][i] == '.') D[i]++;
    }
    for(int i = 1; i <= W-K+1; i++){
      if(X[i+K-1]-X[i-1] == 0) ans = min(ans, D[i+K-1]-D[i-1]);
    }
  }
  for(int x = 1; x <= W; x++){
    for(int i = 1; i <= H; i++){
      X[i] = X[i-1], D[i] = D[i-1];
      if(S[i][x] == 'x') X[i]++;
      if(S[i][x] == '.') D[i]++;
    }
    for(int i = 1; i <= H-K+1; i++){
      if(X[i+K-1]-X[i-1] == 0) ans = min(ans, D[i+K-1]-D[i-1]);
    }
  }
  
  if(ans > K) ans = -1;
  cout << ans << endl;
  return 0;
}