fm.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int R,C,Tr,Tc;
	while(cin >> R >> C >> Tr >> Tc) {
		vector< vector<int> > A(R+2*Tr,vector<int>(C+2*Tc,0));
		for(int i =0; i < R; i++) {
			string s;
			cin >> s;
			for(int j =0; j < C; j++) A[i+Tr][j+Tc] =(int)(s[j] == 'X');}
 
		vector< vector<int> > S(R+2*Tr+1,vector<int>(C+2*Tc+1,0));
		for(int i =0; i < R+2*Tr; i++) for(int j =0; j < C+2*Tc; j++)
			S[i+1][j+1] =S[i][j+1]+S[i+1][j]-S[i][j]+A[i][j];
 
		vector< vector<int> > ans(R+2*Tr,vector<int>(C+2*Tc,0));
		for(int i =R+Tr-1; i >= 0; i--) for(int j =C+Tc-1; j >= 0; j--) {
			int s =S[R+Tr][C+Tc]+S[i][j]-S[i][C+Tc]-S[R+Tr][i];
			int t =S[i+Tr][j+Tc]+S[i][j]-S[i+Tr][j]-S[i][j+Tc];
			ans[i][j] =ans[i+Tr][j]+ans[i][j+Tc]-ans[i+Tr][j+Tc]+(int)(t > 0);}
		int ansT =1000000;
		for(int i =0; i < Tr; i++) for(int j =0; j < Tc; j++) ansT =min(ansT,ans[i][j]);
		cout << ansT << "\n";}
	return 0;}