Since two operation commutes and applying it twice on the same \(i\) has no effect, we can assume that an operation is applied at most one for each \(i\).

In order to extinguish an isolated element, let us determine whether to apply the operation on \(i\) in its ascending order.

Once we determine if we apply the operation on the \(i\)-th row, we can also determine whether any of the \((i-1)\)-th row is isolated or not. On the other hand, any of the rows above is not isolated because the operation on the \(1\)-st, \(2\)-nd, \(\ldots\), and \((i-1)\)-th row is performed while avoiding an isolated element.

Also, whether an element of the \((i-1)\)-th element becomes isolated or not is only dependent on the elements of the \((i-2)\)-th, \((i-1)\)-th, and \(i\)-th rows.

Here, let \(dp_{i,j,k}\) be the minimum number of operations required to be applied on the first \(i\)-th rows so that there is no isolated element on the first \((i-1)\) rows, where \(j\) and \(k\) is a flag expressing whether an operation was performed on the \(i\)-th and \((i-1)\)-th row, respectively.

Then, due to what we have described, this problem can be solved with such a DP (Dynamic Programming). Note that we need to avoid an isolated element in the \(H\)-th row as well, thus taking care of avoiding an isolated element in the \(i\)-th row too when \(i = H\), or let the answer be the minimum value of \(dp_{H,j,k}\) over only appropriate pairs \((j,k)\).

Since this DP has \(O(H)\) states and costs \(O(W)\) time for each transition, the problem has been solved in a total of \(O(HW)\) time.

Sample code

#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
constexpr int inf = 1000000010;
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> a(h, vector<int>(w));
	rep(i, h) rep(j, w) cin >> a[i][j];
	vector<vector<vector<int>>> dp(h, vector<vector<int>>(2, vector<int>(2, inf)));
	dp[0][0][0] = 0;
	dp[0][0][1] = 1;
	for (int i = 1; i < h; i++) {
		rep(j, 2) {
			rep(k, 2) {
				rep(l, 2) {
					vector<int> x(w, -1);
					if (i != 1) x = a[i - 2];
					if (j) rep(m, w) x[m] = 1 - x[m];
					vector<int> y = a[i - 1];
					if (k) rep(m, w) y[m] = 1 - y[m];
					vector<int> z = a[i];
					if (l) rep(m, w) z[m] = 1 - z[m];
					bool ok = true;
					rep(m, w) if (x[m] != y[m] && y[m] != z[m] && (m == 0 || y[m] != y[m - 1]) && (m == w - 1 || y[m] != y[m + 1])) ok = false;
					if (i == h - 1) {
						rep(m, w) if (z[m] != y[m] && (m == 0 || z[m] != z[m - 1]) && (m == w - 1 || z[m] != z[m + 1])) ok = false;
					}
					if (ok) chmin(dp[i][k][l], dp[i - 1][j][k] + l);
				}
			}
		}
	}
	int ans = inf;
	rep(j, 2) rep(k, 2) chmin(ans, dp[h - 1][j][k]);
	cout << (ans == inf ? -1 : ans) << '\n';
}