1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct edge_type {
    int to, next, r;
} edge[500005];
int S, T, cnte = 1, h[500005];
int Q[500005];
void ins(int u, int v, int f) {
    ++cnte;
    edge[cnte].to = v;
    edge[cnte].r = f;
    edge[cnte].next = h[u];
    h[u] = cnte;
    ++cnte;
    edge[cnte].to = u;
    edge[cnte].r = 0;
    edge[cnte].next = h[v];
    h[v] = cnte;
}
int tail, head, d[500005], cur[500005];
bool bfs() {
    tail = head = 0;
    for (int i = S; i <= T; ++i) d[i] = -1;
    Q[tail++] = S;
    d[S] = 0;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (d[edge[i].to] == -1 && edge[i].r) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return d[T] != -1;
}
int dfs(int now, int a) {
    if (T == now || a == 0) return a;
    int ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now]+1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            a -= f;
            ret += f;
            edge[i].r -= f;
            edge[i^1].r += f;
            if (a == 0) break;
        }
    }
    if (ret == 0) d[now] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    while (bfs()) {
        for (int i = S; i <= T; ++i)
            cur[i] = h[i];
        ret += dfs(S, INF);
    }
    return ret;
}
int a[510][510], id[510][510], id2[510][510], n, m, tot;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
			id[i][j] = ++tot;
			if (a[i][j] == 1)
				id2[i][j] = ++tot;
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (a[i][j] == 1) {
				ins(id[i][j], id2[i][j], 1);
				for (int k = 0; k < 4; ++k) {
					int tx1 = i + dx[k], ty1 = j + dy[k],
						tx2 = i + dx[(k+1)%4], ty2 = j + dy[(k+1)%4];
					if (1 <= tx1 && tx1 <= n && 1 <= tx2 && tx2 <= n && 1 <= ty1 && ty1 <= m && 1 <= ty2 && ty2 <= m)
							if (a[tx1][ty1] == 2 && a[tx2][ty2] == 2) {
								if (tx1 & 1)
									ins(id[tx1][ty1], id[i][j], 1),
									ins(id2[i][j], id[tx2][ty2], 1);
								else 
									ins(id[tx2][ty2], id[i][j], 1),
									ins(id2[i][j], id[tx1][ty1], 1);
							}
				}
			}
	S = 0; T = ++tot;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == 2) {
				if (i & 1) ins(S, id[i][j], 1);
				else ins(id[i][j], T, 1);
			}
		}
	int ans = Dinic();
	printf("%d", ans);
    return 0;
}