Submission #37509559

---

Source Code Expand

#include <cstring>
#include <cstdio>
namespace io {
	int c, t, s[100];
	template <typename T> inline void read(T& x) {
		x = 0;
		t = 0;
		c = getchar();
		while (c < 48 || c > 57) {
			if (c == 45) t = 1;
			c = getchar();
		}
		while (c >= 48 && c <= 57) {
			x = (x << 3) + (x << 1) + (c ^ 48);
			c = getchar();
		}
		if (t) x = -x;
	}
	template <typename T> inline void write(T x) {
		if (x) {
			if (x < 0) {
				putchar(45);
				x = -x;
			}
			t = 0;
			while (x) {
				s[t++] = x % 10;
				x /= 10;
			}
			while (t--) {
				putchar(s[t] ^ 48);
			}
		} else {
			putchar(48);
		}
		putchar(10);
	}
}
using io::read;
using io::write;
const int _ = 1e3 + 10;
bool a[_][_], b[_][2][2], l[2], r[2], tmp;
int n, m, k, f[_][2][2], ans;
inline void cmin(int& a, int b) {
	if (a > b) a = b;
}
int main() {
	read(n);
	read(m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			read(k);
			a[i][j] = k;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (((j == 1 || a[i][j] != a[i][j-1])) && ((j == m || a[i][j] != a[i][j+1]))) {
				if (i == 1) {
					l[a[i][j] ^ a[i+1][j]] = true;
				} else if (i == n) {
					r[a[i][j] ^ a[i-1][j]] = true;
				} else {
					b[i][a[i][j] ^ a[i-1][j]][a[i][j] ^ a[i+1][j]] = true;
				}
			}
		}
	}
	memset(f, 0x3F, sizeof(f));
	for (int x = 0; x <= 1; x++) {
		for (int y = 0; y <= 1; y++) {
			tmp = true;
			for (int p = 0; p <= 1; p++) {
				if (l[p] && (!((x ^ y) == p))) tmp = false;
			}
			if (tmp) f[2][x][y] = (x + y);
		}
	}
	for (int i = 2; i < n; i++) {
		for (int x = 0; x <= 1; x++) {
			for (int y = 0; y <= 1; y++) {
				for (int z = 0; z <= 1; z++) {
					if (f[i][x][y] != 0x3F3F3F3F) {
						tmp = true;
						for (int p = 0; p <= 1; p++) {
							for (int q = 0; q <= 1; q++) {
								if (b[i][p][q] && (!(((x ^ y) == p) || ((y ^ z) == q)))) tmp = false;
							}
						}
						if (tmp) cmin(f[i+1][y][z], f[i][x][y] + z);
					}
				}
			}
		}
	}
	ans = 0x3F3F3F3F;
	for (int x = 0; x <= 1; x++) {
		for (int y = 0; y <= 1; y++) {
			tmp = true;
			for (int p = 0; p <= 1; p++) {
				if (r[p] && (!((x ^ y) == p))) tmp = false;
			}
			if (tmp) cmin(ans, f[n][x][y]);
		}
	}
	if (ans == 0x3F3F3F3F) ans = -1;
	write(ans);
	return 0;
}

Submission Info

Judge Result