23 months ago

Manas Bhargava • 0

Mumbai

Which college?

11 days ago

Sourav Mohapatra • 0

Dhanbad

This is the solution for question 3 if anyone wants

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        bool ok = false;
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '1') ok = true;
        }
        if (!ok) {
            cout << "-1\n";
            return 0;
        }
    }
    // ok now at least answer is possible
    vector<vector<int>> cost(n, vector<int>(m, 1e9));
    for (int i = 0; i < n; i++) {
        const string& c = a[i];
        vector<bool> vis(m, false);
        queue<int> q;
        for (int j = 0; j < m; j++) {
            if (c[j] == '1') {
                cost[i][j] = 0;
                vis[j] = true;
                q.push(j);
            }
        }
        while (!q.empty()) {
            int j = q.front();
            q.pop();

            int x = (j + 1) % m;
            int y = (m + j - 1) % m;
            if (!vis[x]) {
                cost[i][x] = cost[i][j] + 1;
                vis[x] = true;
                q.push(x);
            }
            if (!vis[y]) {
                cost[i][y] = cost[i][j] + 1;
                vis[y] = true;
                q.push(y);
            }
        }
    }

    int ans = 1e9;
    for (int j = 0; j < m; j++) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += cost[i][j];
        }
        ans = min(ans, res);
    }

    cout << ans << "\n";
}