761C - Dasha and Password - CodeForces Solution

#include <bits/stdc++.h>
#define int long long    
#define ll long long
#define pb push_back
#define endl "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define lld long double
#define ff first
#define ss second 
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define setbits(x) __builtin_popcountll(x)
#define gcd(a,b) __gcd(a,b)
#define printv(v) for (std::vector<ll>::iterator i = v.begin(); i != v.end(); ++i) cout << *i << " "; cout << endl;
#define vi vector<ll>
#define pii pair<ll,ll>
#define scanv(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
#define inf 1e18


using namespace std;

const ll mod = 1e9 + 7;
const lld pi=3.1415926535897932;

void yesno(bool b) {if(b) cout << "Yes\n";else cout << "No\n";}
void YESNO(bool b) {if(b) cout << "YES\n";else cout << "NO\n";}

int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}

void case_no(ll t){
  static ll a = t;
  cout << "Case #" << a-t+1 << " : \n";
}

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  
    cout.tie(NULL); 
}

inline bool check_num(char c){
    if((c>='0')&&(c<='9')) return true;
    else return false;
}

inline bool check_letter(char c){
    if((c>='a')&&(c<='z')) return true;
    else return false;
}

inline bool check_symbol(char c){
    if((c=='*')||(c=='#')||(c=='&')) return true;
    else return false;
}

ll n,m;

ll dp[51][2][2][2];

ll func(ll i, bool num, bool alph, bool sym, vector<vi> &pos){
    if(i<0) {
        if(num&&alph&&sym) return 0;
        else return inf;
    }
    if(dp[i][num][alph][sym]!=-1) return dp[i][num][alph][sym];
    ll ans1,ans2,ans3;
    ans1 = pos[i][0] + func(i-1,true,alph,sym,pos);
    ans2 = pos[i][1] + func(i-1,num,true,sym,pos);
    ans3 = pos[i][2] + func(i-1,num,alph,true,pos);
    return dp[i][num][alph][sym] = min(ans1,min(ans2,ans3));
}

void solve(){
    cin >> n >> m;
    vector<string> vec_str(n);
    scanv(vec_str);
    vector<vi> pos(n,vi(3,inf));
    /*
       For pos vec
       0 -> number
       1 -> alphabet
       2 -> symbol
    */
    rep(i,n){
        rep(j,m){
            if(check_num(vec_str[i][j])) {
                pos[i][0] = min(pos[i][0],min(j,m-j));
            }
            else if(check_letter(vec_str[i][j])) {
                pos[i][1] = min(pos[i][1],min(j,m-j));
            }
            else {
                pos[i][2] = min(pos[i][2],min(j,m-j));
            }
        }
    }
    rep(i,n+1) rep(j,2) rep(k,2) rep(h,2) dp[i][j][k][h] = -1;
    cout << func(n-1,0,0,0,pos);
}

int32_t main()
{
   fast();
   solve();
   return 0;
}