fm.cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
#define PB push_back
#define MP make_pair
#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
int w, h, tw, th;
char map1[1207][1207];
char map2[1207][1207];
char map3[1207][1207];
int main ()
{
while(scanf("%d%d%d%d", &h, &w, &th, &tw) == 4) {
FOR(i,0,1207) FOR(j,0,1207) map1[i][j] = map2[i][j] = map3[i][j] = '.';
int full;
FOR(r,0,h) {
scanf("%s", &(map1[r+th][tw]));
map1[r+th][w+tw] = '.';
}
w += 2*tw;
h += 2*th;
FOR(r,0,h) {
full = 0;
FORDE(c,w-1,0) {
if(map1[r][c] == 'X') full++;
if(c+tw < w && map1[r][c+tw] == 'X') full--;
if(full == 0) map2[r][c] = '.';
else map2[r][c] = 'X';
}
}
FOR(c,0,w) {
full = 0;
FORDE(r,h-1,0) {
if(map2[r][c] == 'X') full++;
if(r+th < h && map2[r+th][c] == 'X') full--;
if(full == 0) map3[r][c] = '.';
else map3[r][c] = 'X';
}
}
int mi = 1000000000;
FOR(dr,0,th) {
FOR(dc,0,tw) {
int sum = 0;
for(int r = dr; r < h; r += th) {
for(int c = dc; c < w; c += tw) {
if(map3[r][c] == 'X') sum++;
}
}
mi = min(mi,sum);
}
}
printf("%d\n", mi);
/*
FOR(r,0,h) {
FOR(c,0,w) {
printf("%c", map1[r][c]);
}
printf("\n");
}
printf("\n");
FOR(r,0,h) {
FOR(c,0,w) {
printf("%c", map2[r][c]);
}
printf("\n");
}
printf("\n");
FOR(r,0,h) {
FOR(c,0,w) {
printf("%c", map3[r][c]);
}
printf("\n");
}
printf("\n");
*/
}
return 0;
}