1680E - Moving Chips - CodeForces Solution

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int (i)=(a);(i)<(b); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

//Replace I and O with the input and output type
typedef vector<string> I;
typedef int O;

O smart(I &input) {
    int l = 0, r = input[0].size()-1;
    while(input[0][l] != '*' and input[1][l] != '*')
        ++l;
    while(input[0][r] != '*' and input[1][r] != '*')
        --r;

    vector<string> fixed(2);
    fixed[0] = input[0].substr(l, r-l+1);
    fixed[1] = input[1].substr(l, r-l+1);

    vector<vi> dp(2, vi(fixed[0].size()));
    dp[0][0] = fixed[1][0] == '*';
    dp[1][0] = fixed[0][0] == '*';
    for(int i=1;i<fixed[0].size();++i) {
        dp[0][i] = min(2+dp[1][i-1], 1+dp[0][i-1]+(fixed[1][i] == '*'));
        dp[1][i] = min(2+dp[0][i-1], 1+dp[1][i-1]+(fixed[0][i] == '*'));
    }
    return min(dp[0].back(), dp[1].back());
}


O dumb(I &input) {
}

//Read input from the keyboard
I get() {
    int n;
    cin>>n;
    vector<string> grid(2);
    cin >> grid[0] >> grid[1];
    return grid;
}

//Generate random test cases
I gen() {
;
}

//Print input to the screen
void print(I &input) {
    cout << "Input\n-------\n";
    cout << input[0].size() << endl;
    cout << input[0] << endl;
    cout << input[1] << endl;
}

//Print output to the screen
void print(O &output) {
    cout << output << endl;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    cin>>t;
    while(t--) {
        I input = get();//replace with gen()
        O s = smart(input);//O d = dumb(forDumb);

        print(s);


    }
}