Submission #2387394

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct edge {
	int to, cap, rev;
};

vector<edge>G[7777]; bool used[7777]; int H, W;

void add_edge(int p1, int p2, int p3) {
	if (p1 < H*W && p2 < H*W) {
		if (((p1 / W) + (p1%W)) % 2 == 1) swap(p1, p2);
	}
	G[p1].push_back(edge{ p2,p3,(int)G[p2].size() });
	G[p2].push_back(edge{ p1,0,(int)G[p1].size() - 1 });
}
int dfs(int pos, int to, int cap) {
	if (pos == to) return cap;
	used[pos] = true;
	for (int i = 0; i < G[pos].size(); i++) {
		if (used[G[pos][i].to] == true || G[pos][i].cap == 0) continue;
		int V = dfs(G[pos][i].to, to, min(cap, G[pos][i].cap));
		if (V == 0) continue;
		G[pos][i].cap -= V;
		G[G[pos][i].to][G[pos][i].rev].cap += V;
		return V;
	}
	return 0;
}
int max_flow(int u, int v) {
	int fl = 0;
	while (true) {
		for (int i = 0; i < 7777; i++) used[i] = false;
		int C = dfs(u, v, 1000000007);
		if (C == 0) break;
		fl += C;
	}
	return fl;
}

int a[77][77], b[77][77], l[77][77], cost;

int main() {
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) { cin >> a[i][j]; l[i][j] = (i - 1)*W + (j - 1); }
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> b[i][j];
			if (a[i][j] != b[i][j]) cost++;
		}
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (i <= H - 1 && a[i][j] != b[i][j] && a[i + 1][j] != b[i + 1][j] && a[i][j] != a[i + 1][j]) add_edge(l[i][j], l[i + 1][j], 1);
			if (j <= W - 1 && a[i][j] != b[i][j] && a[i][j + 1] != b[i][j + 1] && a[i][j] != a[i][j + 1]) add_edge(l[i][j], l[i][j + 1], 1);
			if ((i + j) % 2 == 0) add_edge(H*W, l[i][j], 1);
			if ((i + j) % 2 == 1) add_edge(l[i][j], H*W + 1, 1);
		}
	}
	int GG = max_flow(H*W, H*W + 1);
	cout << cost - GG << endl;
	return 0;
}

Submission Info

Judge Result