1T 2M 求卡时空

#include <iostream>
#include <algorithm>
#include <unordered_map>

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;

int lim;

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

int main () {
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			char inp;
			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 (114514 < 1919810) {
		if (IDAstar(0, stt)) {
			cout << lim;
			return 0;
		}
		lim ++;
	}
	return 0;
}