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>
 
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 MAXN = 1400;
bool input[MAXN][MAXN];
bool rowmax[MAXN][MAXN];
bool cellmax[MAXN][MAXN];
 
int AR, AC, TR, TC;
 
int main() {
	while (scanf("%d%d%d%d ", &AR, &AC, &TR, &TC) == 4) {
		REP(i,AR) {
			char *line = 0;
			size_t size;
			getline(&line, &size, stdin);
			DEBUG(line);
			REP(j,AC) input[i][j] = (line[j] == 'X');
			free(line);
		}
		REP(r,AR) {
			int sum = 0;
			int begin = -TC;
			int end = 0;
			while (end < AC+TC) {
				if (begin >= 0) sum -= input[r][begin];
				sum += input[r][end];
				rowmax[r][end] = (sum > 0);
				++begin; ++end;
			}
		}
		REP(c,AC+TC) {
			int sum = 0;
			int begin = -TR;
			int end = 0;
			while (end < AR+TR) {
				if (begin >= 0) sum -= rowmax[begin][c];
				sum += rowmax[end][c];
				cellmax[end][c] = (sum > 0);
				++begin; ++end;
			}
		}
		int best = INF;
		REP(sc,TC) REP(sr,TR) {
			int cnt = 0;
			int r = sr;
			while (r < AR+TR) {
				int c = sc;
				while (c < AC+TC) {
					cnt += (cellmax[r][c] ? 1 : 0);
					c += TC;
				}
				r += TR;
			}
			DEBUG(sc);
			DEBUG(sr);
			DEBUG(cnt);
			if (cnt < best) best = cnt;
		}
		printf("%d\n", best);
	}
	return 0;
}