题解：
经典的状压预处理问题，可以知道在$n=10$下单行只会有$169$种合法状态。
那么就可以套用状压进行解决。

本题时限$5s$，实际在测时，将所有的不合法情况在每一层可判时及时判掉后，
就会跑的飞快，从$4539ms$到$93ms$。

代码：

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

#define sz(x) (int)x.size()
typedef long long ll;

const int N = 110, M = 1 << 10, S = 169;
int n, m;
int g[N];
int cnt[M];
int ok[S], s;
int f[2][S][S];

bool check(int x) {
    if(x & (x << 2)) return false;
    return true;
}

bool checkab(int x, int y) {
    if(x & (y << 1)) return false;
    if(x & (y >> 1)) return false;
    return true;
}

int count(int x) {
    int res = 0;
    for(int i = 0; i < m; ++i) res += x >> i & 1;
    return res;
}

void solve() {
    s = 0; 
    memset(cnt, 0, sizeof cnt);
    memset(g, 0, sizeof g);
    memset(f, 0, sizeof f);
    for(int i = 1, x; i <= n; ++i) 
        for(int j = 0; j < m; ++j) { 
            scanf("%d", &x);
            if(!x) g[i] += (1 << j);
        } 

    for(int i = 0; i < 1 << m; ++i)
        if(check(i)) ok[s] = i, cnt[s] = count(i), ++s;

    for(int i = 1; i <= n; ++i)
        for(int a = 0; a < s; ++a) { 
            int x = ok[a];
            if(g[i] & x) continue; 
            for(int b = 0; b < s; ++b) { 
                int y = ok[b];
                if(g[i - 1] & y) continue;
                if(!checkab(x, y)) continue;
                for(int c = 0; c < s; ++c) {
                    int z = ok[c];
                    if((x & z) || (!checkab(y, z))) continue;
                    f[i & 1][b][a] = max(f[i & 1][b][a], f[(i - 1) & 1][c][b] + cnt[a]);
                }
            }
        } 
    int res = 0;
    for(int a = 0; a < s; ++a)
        for(int b = 0; b < s; ++b)
            res = max(res, f[n & 1][a][b]);

    printf("%d\n", res);
}

int main()
{

    while(~scanf("%d%d", &n, &m)) solve();

    return 0;
}