speedrun.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
#define FOR(i,j,k) for(int i=j; i<k; ++i)
#define look(a) cerr <<#a<<": "<<a<<endl;
#define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;

string a[20];
int l[20],r[20];
int n,m,top = -1,ans = 1e18, s;

void scan()
{
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m+2; ++j)
            if (a[i][j] == '1'){
                r[i] = j;
                if (top == -1) top = i;
            }
        for (int j = m+1; j >= 0; --j)
            if (a[i][j] == '1')
                l[i] = j;
    }
}

void dq(int i, int p)
{
    if (i == top) ans = min(ans,s);
    else {
        s += p + r[i-1] + 1;
        dq(i-1,r[i-1]);
        s -= p + r[i-1] + 1;
        s += 2*(m+1) - p - l[i-1] + 1;
        dq(i-1,l[i-1]);
        s -= 2*(m+1) - p - l[i-1] + 1;
    }
}

void solve()
{
    cin >> n >> m;
    FOR(i,0,n)
        cin >> a[i];
    FOR(i,0,n) l[i] = m+1;
    scan();
    if (top == -1){
        cout << 0;
        return;
    }
    s = r[n-1];
    dq(n-1,r[n-1]);
    cout << ans;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
        cout << '\n';
    }
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}