IDA* 92pts 求卡常或优化

#include <algorithm>

using namespace std;

constexpr int N = 10;
int n = 9;
constexpr int bel[10][10] = {
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};
struct Situ {
	bool h[N], l[N], k[N];
	int sumh, suml, sumk;
} stt, tmp;

int lim;

bool IDAstar (int step) {
	if (max({tmp.sumh, tmp.suml, tmp.sumk}) + step > lim) return false;
	if (tmp.sumh + tmp.suml + tmp.sumk == 0) return true;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			tmp.sumh += (tmp.h[i] ? -1 : 1);
			tmp.suml += (tmp.l[j] ? -1 : 1);
			tmp.sumk += (tmp.k[bel[i][j]] ? -1 : 1);
			tmp.h[i] ^= 1;
			tmp.l[j] ^= 1;
			tmp.k[bel[i][j]] ^= 1;
			if (IDAstar(step + 1)) return true;
			tmp.sumh += (tmp.h[i] ? -1 : 1);
			tmp.suml += (tmp.l[j] ? -1 : 1);
			tmp.sumk += (tmp.k[bel[i][j]] ? -1 : 1);
			tmp.h[i] ^= 1;
			tmp.l[j] ^= 1;
			tmp.k[bel[i][j]] ^= 1;
		}
	}
	return false;
}

int main () {
	char inp;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			cin >> inp;
			if (inp == '1') {
				stt.sumh += (stt.h[i] ? -1 : 1);
				stt.suml += (stt.l[j] ? -1 : 1);
				stt.sumk += (stt.k[bel[i][j]] ? -1 : 1);
				stt.h[i] ^= 1;
				stt.l[j] ^= 1;
				stt.k[bel[i][j]] ^= 1;
			}
		}
	}
	while (lim < 9) {
		tmp = stt;
		cerr << lim << '\n';
		if (IDAstar(0)) {
			cout << lim;
			return 0;
		}
		lim ++;
	}
	cout << '9';
	return 0;
}
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int N = 10;
int n = 9;
constexpr int bel[10][10] = {
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
	{0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};
struct Situ {
	bool h[N], l[N], k[N];
	int sumh, suml, sumk;
} stt, tmp;

int lim;

bool IDAstar (int step) {
	if (max({tmp.sumh, tmp.suml, tmp.sumk}) + step > lim) return false;
	if (tmp.sumh + tmp.suml + tmp.sumk == 0) return true;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			tmp.sumh += (tmp.h[i] ? -1 : 1);
			tmp.suml += (tmp.l[j] ? -1 : 1);
			tmp.sumk += (tmp.k[bel[i][j]] ? -1 : 1);
			tmp.h[i] ^= 1;
			tmp.l[j] ^= 1;
			tmp.k[bel[i][j]] ^= 1;
			if (IDAstar(step + 1)) return true;
			tmp.sumh += (tmp.h[i] ? -1 : 1);
			tmp.suml += (tmp.l[j] ? -1 : 1);
			tmp.sumk += (tmp.k[bel[i][j]] ? -1 : 1);
			tmp.h[i] ^= 1;
			tmp.l[j] ^= 1;
			tmp.k[bel[i][j]] ^= 1;
		}
	}
	return false;
}

int main () {
	char inp;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			cin >> inp;
			if (inp == '1') {
				stt.sumh += (stt.h[i] ? -1 : 1);
				stt.suml += (stt.l[j] ? -1 : 1);
				stt.sumk += (stt.k[bel[i][j]] ? -1 : 1);
				stt.h[i] ^= 1;
				stt.l[j] ^= 1;
				stt.k[bel[i][j]] ^= 1;
			}
		}
	}
	while (lim < 9) {
		tmp = stt;
		cerr << lim << '\n';
		if (IDAstar(0)) {
			cout << lim;
			return 0;
		}
		lim ++;
	}
	cout << '9';
	return 0;
}