ABC283E WA

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;
int h, w;

bool check(const vector<vector<int>> &v, int i, int op1, int op2, int op3)
{
    bool ret = true;
    int dir[3][2] = {{0, 1}, {1, 0}, {-1, 0}};
    for (int j = 0; j < w && ret; ++j) {
        bool jflag = false;
        for (int p = 0; p < 3; ++p) {
            int nx = i + dir[p][0], ny = j + dir[p][1];
            if (nx >= 0 && nx < w && ny >= 0 && ny <= h) {
                if ((v[i][j] ^ op1) == (v[nx][ny] ^ (ny == i + 1 ? op2 : op1))) {
                    jflag = true;
                }
            }
        }
        if ((v[i][j] ^ op1) == (v[i - 1][j] ^ op3))
            jflag = true;
        ret = ret & jflag;
    }
    return ret;
}

int main(int argc, char **argv)
{
    cin >> h >> w;
    auto a = vv<int>(h, w);
    for (auto &row : a)
        for (auto &col : row)
            cin >> col;

    a.insert(a.begin(), vi(w, -1));
    a.push_back(vi(w, -1));

    // the minimum operations needed to have i-th row legit
    // j: flip flag on i-th row
    // k: flip flag on (i+1)-th row
    // dp[i][j][k];

    vector<array<int, 4>> dp(h + 2, array<int, 4>{INT_MAX / 2, INT_MAX / 2, INT_MAX / 2, INT_MAX / 2});
    dp[0][0] = 0;
    dp[0][1] = 1;
    dp[0][2] = 1;
    dp[0][3] = 2;

    for (int i = 1; i <= h; ++i) {
        for (int s = 0; s < 4; ++s) {
            int op1 = s / 2;
            int op2 = s % 2;
            for (int op3 = 0; op3 <= 1; ++op3) {
                if (check(a, i, op2, op3, op1))
                    dp[i][op2 * 2 + op3] = min(dp[i][op2 * 2 + op3], dp[i - 1][op1 * 2 + op2] + op3);
            }
        }
    }
    int min_val = min({dp[h][0], dp[h][1], dp[h][2], dp[h][3]});
    cout << (min_val == INT_MAX / 2 ? -1 : min_val) << endl;
    return 0;
};