turnofflights.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>

#define long long long
#define nln '\n'

using namespace std;

pair<long, long> locate(
    const vector<string> &flr,
    long m, long pst)
{
    long lef, rig;
    if ((long)flr[pst].find('1') == -1)
        lef = m+1, rig = 0;
    else
    {
        lef = flr[pst].find('1');
        string tem = flr[pst];
        reverse(tem.begin(), tem.end());
        rig = m+1-tem.find('1');
    }
    return {lef, rig};
}

void visit(
    const vector<string> &flr,
    long pst, long csm, long &ans,
    long fin, long sta, long m)
{
    if (sta <= fin)
    {
        ans = (csm < ans) ? csm : ans;
        return;
    }
    pair<long, long> dtc = locate(flr, m, sta-1);
    string tem = flr[sta-1];
    reverse(tem.begin(), tem.end());
    visit(flr, dtc.first, csm+(m+1-pst)+(m+1-dtc.first)+1, ans, fin, sta-1, m);
    visit(flr, dtc.second, csm+pst+dtc.second+1, ans, fin, sta-1, m);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    // Input
    //freopen("turnofflights.inp", "r", stdin);
    long n, m;
    cin >> n >> m;
    vector<string> flr(n);
    for (auto &i : flr)
        cin >> i;
    // Process
    // Find lowest floor has light on.
    long sta = n-1, csm = 0;
    while (sta >= 0 && (long)flr[sta].find('1') == -1)
        --sta, ++csm;
    if (sta < 0)
    {
        cout << 0 << nln;
        return 0;
    }
    // Find last floor has light on
    long fin = sta;
    for (long i = 0; i <= sta; ++i)
        if (flr[i].find('1') < flr[i].size())
        {
            fin = i;
            break;
        }
    // Start to turn off light in buildings
    long ans = LLONG_MAX;
    visit(flr, locate(flr, m, sta).second, locate(flr, m, sta).second+csm, ans, fin, sta, m);
    cout << ans << nln;
    return 0;
}