fm.cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
vector<vector<char> > mapka;
vector<int> intervalac;
int AR,AC,TR,TC, mocnina;
int spusti(int vrchol, pair<int,int> LH, pair<int,int> PD){
if(PD.first-LH.first==1) {
if(mapka[LH.first][LH.second]=='X') {
intervalac[vrchol] = 1;
return 1;
}
else return 0;
}
intervalac[vrchol] = spusti(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2))
+ spusti(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2))
+ spusti(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second))
+ spusti(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD);
return intervalac[vrchol];
}
int pocet(int vrchol, pair<int,int> LH, pair<int,int> PD, pair<int,int> HlaLH, pair<int,int> HlaPD){
if(HlaLH.first <= LH.first && HlaLH.second <= LH.second && HlaPD.first >= PD.first && HlaPD.second >= PD.second)
return intervalac[vrchol];
else if (HlaLH.first >= PD.first || HlaLH.second >= PD.second || HlaPD.first <= LH.first || HlaPD.second <= LH.second) return 0;
else {
return pocet(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), HlaLH, HlaPD)
+ pocet(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2), HlaLH, HlaPD)
+ pocet(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second), HlaLH, HlaPD)
+ pocet(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD, HlaLH, HlaPD);
}
}
int skus(int x, int y){
int vys = 0;
for(int i = x; i + TR < mocnina; i += TR){
for(int j = y; j + TC < mocnina; j += TC){
//cout<<"od: ["<<i<<", "<<j<<"] po ["<<i+TR<<", "<<j+TC<<"] to je "<<pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC))<<endl;
if(pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC)) > 0) vys++;
}
}
return vys;
}
int main(){
while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){
mapka.clear();
intervalac.clear();
mocnina = 1;
while(mocnina < TR+TR+AR+TR+TR) mocnina *= 2;
while(mocnina < TC+TC+AC+TC+TC) mocnina *= 2;
mapka.resize(mocnina, vector<char> (mocnina,'.'));
intervalac.resize(mocnina * mocnina * 2, 0);
for(int i = 0; i < AR; i++){
string riadok;
cin>>riadok;
for(int j = 0; j < riadok.size(); j++){
mapka[i + TR * 2][j + TC * 2] = riadok[j];
}
}
spusti(0,make_pair(0,0), make_pair(mocnina, mocnina));
/* for(int i = 0; i < mocnina; i++){
for(int j=0; j< mocnina; j++){
cout<<mapka[i][j];
}
cout<<endl;
}
for(int i =0; i< mocnina * mocnina ; i++){
cout<<intervalac[i]<<" ";
}*/
int najmensie = 100000000;
for(int i = 0; i < TR; i++){
for(int j = 0; j < TC; j++){
najmensie = min(skus(i,j), najmensie);
}
}
cout<<najmensie<<endl;
}
}