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

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct UF {
    vi e, l, r;
    UF(int n) : e(n, -1), l(n), r(n) {
        iota(all(l), 0);
        iota(all(r), 0);
    }
    bool sameSet(int a, int b) { return find(a) == find(b); }
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        l[a] = min(l[a], l[b]);
        r[a] = max(r[a], r[b]);
        e[a] += e[b]; e[b] = a;
        return true;
    }
};
int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for(auto &s : a) {
        cin >> s;
    }
    if(!(n >= m)) {
        vector<string> b(m);
        for(auto &i : b) i.resize(n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                b[j][i] = a[i][j];
        swap(n, m);
        a = b;
    }//n >= m

    vector F(m, vector<int>(m, 1ll<<30));
    F[0][m - 1] = 0;
    for(int len = m - 1; len; len--) {
        for(int start = 0; start + len <= m; start++) {
            int end = start + len - 1;
            F[start][end] = 1 + min(
                    F[max(start - len, 0)][end],
                    F[start][min(end + len, m - 1)]
            );
        }
    }

    const int L = 25;
    array<vector<int>, L> G;
    G.fill(vector<int>(n, -1));

    vector<int> die(m, n);
    vector<int> ord(m); iota(all(ord), 0);
    for(int start = n; start--;) {
        for(int j = 0; j < m; j++) {
            if(a[start][j] == '0')
                die[j] = start;
        }
        sort(all(ord), [&](int x, int y) {
            return die[x] > die[y];
        });
        // for(int i = 0; i < m; i++) cout << die[i] << " "; cout << endl;

        UF d(m);
        vector<int> alive(m);
        int end = n, ans = 1<<30;
        for(auto i : ord) {
            end = die[i] - 1;
            if(end < start) break;
            alive[i] = 1;
            if(i && alive[i - 1]) d.join(i - 1, i);
            if(i + 1 < m && alive[i + 1]) d.join(i, i + 1);

            i = d.find(i);
            ans = min(ans, F[d.l[i]][d.r[i]]);
            G[ans][start] = max(G[ans][start], end);
            // cout << start << " " << end << "(" << i << ") :: " << ans << endl;
        }
    }

    for(int ops = 0; ops < L; ops++) {
        if(G[ops][0] >= n - 1) {
            cout << ops << '\n';
            return 0;
        }
        for(int start = 0; start < n; start++) if(G[ops][start] != -1) {
            int len = G[ops][start] - start + 1;
            G[ops + 1][start] = max(G[ops+1][start],
                                    min(G[ops][start] + len, n - 1));
            G[ops + 1][max(start - len, 0)] = max(G[ops+1][max(start - len, 0)],
                                                  G[ops][start]);
        }
    }
}