225C - Barcode - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;
int n,m,x,y,dots[1005],a[1005][1005],dp[1005][1005][3];
int solve(int col,int width,int prev){
    if (col==m){
        if(width < x || width > y)
            return INF;
        return 0;
    }
    int &ret=dp[col][width][prev];
    if (~ret) return ret;
    int choise1=INF,choise2=INF;
    if (col==0||(prev== 0 && width+1 <= y)||(prev==1&&width>=x)){
        if (prev==0){
            choise1=n-dots[col]+solve(col+1,width+1,0);
        }
       else choise1=n-dots[col]+solve(col+1,1,0);
    }
    if (col==0||(prev== 1 && width+1 <= y)||(prev==0&&width>=x)){
        if (prev==1){
            choise2=dots[col]+solve(col+1,width+1,1);
        }
        else choise2=dots[col]+solve(col+1,1,1);
    }
    return ret=min(choise1,choise2);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);
    memset(dp,-1,sizeof(dp));
    cin>>n>>m>>x>>y;
    char ch;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin>>ch;
            if(ch == '.')
                dots[j]++;
        }
    }
    cout<<solve(0,0,2);
//

}