ある行 \(a_{i}\) に孤立点が無いという判定を考える． これは，前後の行の影響を受け，それ以外の行は影響を受けない． よって，2行分の情報が必要なので，それを覚えながらDP.
注意は， \(a_{i}\) の時点では孤立点がなくても， \(a_{i+1}\) 次第では \(a_{i}\) の孤立点を消せる場合があること． よって， for \(i \in H\) で考えるときは， \(a_{i-1}\) を孤立点無しで確定させる，という方針にする．
実装
最初の2行は個別に計算． また， for \(i \in [2,H)\) が終わった後は， 最後の1行に孤立点が無いかは判定していない． よって，答えを出すときに判定する． 形式的に， \(-1,H\) 行目は全て-1の行とみなすと楽．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w; cin >> h >> w;
vvll a(h, vll(w)); cinvv(a);
auto get = [&](int i, bool flip) -> vll {
vll ret(w);
rep(j,w) ret[j] = a[i][j]^flip;
return ret;
};
// check b1 is good
auto check = [&](const vll &c, const vll &b1, const vll &b2) -> bool {
rep(i,w){
if(b1[i] == c[i]) continue;
if(b1[i] == b2[i]) continue;
if(i && b1[i] == b1[i-1]) continue;
if(i+1 < w && b1[i] == b1[i+1]) continue;
return false;
}
return true;
};
vll dp(4, INFL);
rep(s,4){
vll b2 = vll(w, -1);
vll b1 = get(0, s&2);
vll c = get(1, s&1);
ll cnt = pcntll(s);
if(check(c, b1, b2)) chmin(dp[s], cnt);
}
srep(i,2,h){
vll old(4, INFL);
swap(old, dp);
rep(s,4){
vll b2 = get(i-2, s&2);
vll b1 = get(i-1, s&1);
ll cnt = pcntll(s);
rep(f,2){
vll c = get(i, f);
}
}
}
// この時点では，最後の1行 a[H-1]に孤立点が無いか不明なので，
// 答えを出すときに判定する．
ll ans = INFL;
rep(s,4){
vll b2 = get(h-2, s&2);
vll b1 = get(h-1, s&1);
vll c(w, -1);
if(check(c, b1, b2)) chmin(ans, dp[s]);
}
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
*1:s << 1LL) | f) & 3;
if(check(c, b1, b2
