#DP #PickOrLeave #Matrices #Codeforces #Solved

C. Barcode.cpp

//http://codeforces.com/contest/225/problem/C
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;
const int MAX = 1005;
const int OO = (int)1e6;
int a[MAX];
int cache[MAX][2*MAX+5];
int n, m, x, y;

int minBarcode(int i, int pre) {
    if(i == m) {
        if(pre > 0) {
            if(pre < x || pre > y) return OO;
        } else if((-1*pre) < x || (-1*pre) > y) return OO;
        return 0;
    }

    int &ret = cache[i][pre+MAX];
    if(ret != -1) return ret;
    ret = OO;

    //switch column to '.'
    if(pre == OO) { // first column
        ret = min(ret, minBarcode(i+1, 1)+(n-a[i]));
    } else {
        if(pre > 0) {
            if(pre < y)
                ret = min(ret, minBarcode(i+1, pre+1)+(n-a[i]));
        } else {
            if((-1*pre) >= x)
                ret = min(ret, minBarcode(i+1, 1)+(n-a[i]));
        }
    }

    //switch column to '#'
    if(pre == OO) { // first column
        ret = min(ret, minBarcode(i+1, -1) + a[i]);
    } else {
        if(pre < 0) {
            if(pre > (-1*y) )
                ret = min(ret, minBarcode(i+1, pre-1)+ a[i]);
        } else {
            if(pre >= x)
                ret = min(ret, minBarcode(i+1, -1)+ a[i]);
        }
    }

    return ret;
}

int main() {
    cin>>n>>m>>x>>y;
    string tmp;
    clr(a, 0);
    clr(cache, -1);
    lp(i, n) {
        cin>>tmp;
        lp(j, m) {
            if(tmp[j] == '.') a[j]+=1;
        }
    }
    cout << minBarcode(0, OO) << endl;
}