以下では、\(1\) 行 \(W\) 列のグリッドが与えられたときに、グリッド内で横方向に o を \(K\) 個並べることは可能か？可能ならその最小手数は？という問題を \(O(W)\) 時間で解くことを考えます。（元の問題を解くには、それを各行および各列について行えばよく、グリッド全体で \(O(HW)\) 時間で可能です。）

このグリッド内から連続した \(K\) マス \((1, i), (1, i+1), \ldots, (1, i+K-1)\)（以下、単に区間 \([i, i+K-1]\) などと呼ぶ）を選んだとき、これら \(K\) マスをすべて o にすることができるのは、区間 \([i, i+K-1]\) 内に x が無いときかつそのときに限ります。 また、その場合に区間内 \([i, i+K-1]\) を全て o にするための最小手数は、区間内の . の個数と等しいです。

したがって、答えを求めるには \((W-K+1)\) 個の区間 \([1, K], [2, K+1], \ldots, [W-K+1, W]\) 全てについて、その区間内の x の個数と . の個数が分かれば良いです。 これは、x と . の個数それぞれの累積和によって高速に求められます。

具体的には、各 \(i = 0, 1, 2, \ldots, W\) について区間 \([1, i]\) 内の、xの個数を \(X_i\) 、. の個数を \(D_i\) とする配列 \(X, D\) を前計算しておくことで、各区間 \([i, i+K-1]\) 内の x の個数 . の個数はそれぞれ\(X_{i+K-1} - X_{i-1}\) と \(D_{i+K-1} - D_{i-1}\) として \(O(1)\) 時間で求められ、 \((W-K+1)\) 個の区間 \([1, K], [2, K+1], \ldots, [W-K+1, W]\) 全部で計算しても全体 \(O(W)\) 時間で済みます。

以下に、C++ 言語による本問題の正解例を記載します。

#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]; //添字を解説本文と揃えるためだけの便宜上の処理です

  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;
}