题目链接：http://codeforces.com/problemset/problem/225/C
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn =1e3+5;
const int mod=9999991;
int INF;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：给定一个01二维像素图形，
问摆成符合条件的最小花费是多少，
其中符合条件的图形要求是连续像素长度在x和y之间
，0和1都要符合要求。明显用动态规划去处理一下，分析下我们dp
需要的条件，首先是需要一维枚举当前连续的颜色长度的，
然后一维表示位置，这样逻辑就清楚了。dp(i,j,k)表示在i位置其颜色为k 的连续长度为j 的最小花费是多少。
状态转移的话就考虑：
当j为1的时候，枚举x到y进行状态转移更新，
当j不为1的时候，直接利用dp(i-1,j-1,k)进行转移即可。
最后从x到y区间内筛选出答案即可。
*/int n,m,x,y,add;
int mp[maxn][maxn],cnt[maxn];
char s[maxn];
int dp[maxn][maxn][2];
int main()
{scanf("%d%d%d%d",&n,&m,&x,&y);for(int i=0;i<n;i++){scanf("%s",s);for(int j=0;j<m;j++){if(s[j]=='.') mp[i][j]=0,cnt[j]++;else mp[i][j]=1;}}memset(dp,0xf,sizeof(dp));INF=dp[0][0][0];int ans=INF;for(int i=0;i<m;i++){if(i==0){dp[i][1][0]=cnt[i];dp[i][1][1]=n-cnt[i];continue;}for(int j=1;j<=i+1&&j<=y;j++){if(j==1){for(int p=x;p<=y;p++){dp[i][j][0]=min(dp[i][j][0],dp[i-1][p][1]+cnt[i]);dp[i][j][1]=min(dp[i][j][1],dp[i-1][p][0]+n-cnt[i]);}}else{dp[i][j][0]=dp[i-1][j-1][0]+cnt[i];dp[i][j][1]=dp[i-1][j-1][1]+n-cnt[i];}}}for(int i=x;i<=y;i++){ans=min(ans,dp[m-1][i][0]);ans=min(ans,dp[m-1][i][1]);}printf("%d\n",ans);return 0;
}