fm.cpp
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////
const int MAX = 1300;
int R, C, TR, TC;
char in[MAX][MAX];
int sum[MAX][MAX];
int get(int r1, int c1, int r2, int c2)
{
int res = sum[r2][c2];
if (r1) res -= sum[r1-1][c2];
if (c1) res -= sum[r2][c1-1];
if (r1&&c1) res += sum[r1-1][c1-1];
return res;
}
int dp[200][200];
int main()
{
while (scanf("%d%d%d%d", &R, &C, &TR, &TC) == 4)
{
memset(sum, 0, sizeof(sum));
REP(i, R)
{
scanf("%s", in[i]);
REP(j, C) sum[i+TR][j+TC] = in[i][j] == 'X';
}
R += TR;
C += TC;
REP(i, R+TR) REP(j, C+TC)
{
if (i) sum[i][j] += sum[i-1][j];
if (j) sum[i][j] += sum[i][j-1];
if (i&&j) sum[i][j] -= sum[i-1][j-1];
}
memset(dp, 0, sizeof(dp));
REP(i, R) REP(j, C)
{
if (get(i, j, i+TR-1, j+TC-1))
dp[i%TR][j%TC] += 1;
}
int res = INF;
REP(i, TR) REP(j, TC)
res = min(res, dp[i][j]);
printf("%d\n", res);
}
return 0;
}