Language: C++

#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
vector<vector<char>>S;
bool dp[13][160]; int LIM2 = 0;
vector<vector<char>> solve(vector<vector<char>>p, int x, int y, int r) {
	if (r == 1) { p[x][y]--; p[x + 1][y]--; p[x - 1][y]--; p[x][y - 1]--; p[x][y + 1]--; }
	if (r == 2) { for (int i = -1; i <= 1; i++)for (int j = -1; j <= 1; j++)p[x + i][y + j]--; }
	if (r == 3) { for (int i = -1; i <= 1; i++)for (int j = -1; j <= 1; j++)p[x + i][y + j]--; p[x + 2][y]--; p[x][y + 2]--; p[x - 2][y]--; p[x][y - 2]--; }
	return p;
}
bool isgood(int p) {
	if (p % 4 == 1 && p >= 5)return true;
	if (p % 4 == 2 && p >= 10)return true;
	if (p % 4 == 3 && p >= 15)return true;
	if (p % 4 == 0 && p >= 20)return true;
	return false;
}
bool hantei(vector<vector<char>>p) {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (p[i][j] < 0)return false;
		}
	}
	bool OKs[10][10]; for (int i = 0; i < 100; i++)OKs[i / 10][i % 10] = false;
	for (int i = 1; i < 9; i++) {
		for (int j = 1; j < 9; j++) {
			if (p[i][j] == 0)continue;
			if (p[i - 1][j] >= 1 && p[i + 1][j] >= 1 && p[i][j - 1] >= 1 && p[i][j + 1] >= 1) {
				OKs[i][j] = true; OKs[i - 1][j] = true; OKs[i][j - 1] = true; OKs[i][j + 1] = true; OKs[i + 1][j] = true;
			}
			bool OK4 = true;
			for (int k = -1; k <= 1; k++)for (int l = -1; l <= 1; l++)if (p[i + k][j + l] == 0)OK4 = false;
			if (OK4 == false)continue;
			for (int k = -1; k <= 1; k++)for (int l = -1; l <= 1; l++)OKs[i + k][j + l] = true;
		}
	}
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++) {
			if (OKs[i][j] == false && p[i][j] >= 1)return false;
		}
	}
	queue<pair<int, int>>Q3; bool OK5[10][10]; for (int i = 0; i < 100; i++)OK5[i / 10][i % 10] = false;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (p[i][j] == 0 || OK5[i][j] == false)continue;
			vector<int>sc; Q3.push(make_pair(i, j)); OK5[i][j] = true; sc.push_back(p[i][j]);
			int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
			while (!Q3.empty()) {
				int a11 = Q3.front().first, a12 = Q3.front().second; Q3.pop();
				for (int k = 0; k < 4; k++) {
					int cx = a11 + dx[k], cy = a12 + dy[k];
					if (cx < 0 || cx >= 10 || cy < 0 || cy >= 10)continue;
					if (p[cx][cy] == 0 || OK5[cx][cy] == true)continue;
					Q3.push(make_pair(cx, cy)); sc.push_back(p[cx][cy]); OK5[cx][cy] = true;
				}
			}
			int sums = 0; for (int i = 0; i < sc.size(); i++)sums += sc[i];
			if (isgood(sums) == false)return false;
		}
	}
	if (rand() % 10 == 0 && n == 12)return false;
	return true;
}
vector<tuple<vector<vector<char>>, int, vector<tuple<char, char, char>>>>Vec;
void zen_shori() {
	int JJ = 165; if (LIM2 == 2)JJ = 25000;
	for (int i = 0; i < JJ; i++) {
		tuple<vector<vector<char>>, int, vector<tuple<char, char, char>>>ZZ;
		Vec.push_back(ZZ);
	}
	vector<vector<char>>ZERO; int LL = 0, RR = 0;
	vector<tuple<char, char, char>>ZERO3;
	for (int i = 0; i < 10; i++) { vector<char>ZERO5(10, 0); ZERO.push_back(ZERO5); }
	Vec[0] = make_tuple(ZERO, 0, ZERO3); RR++;
	while (LL < RR && RR < JJ) {
		vector<vector<char>>a1 = get<0>(Vec[LL]); int a2 = get<1>(Vec[LL]);
		vector<tuple<char, char, char>>a3 = get<2>(Vec[LL]);
		LL++; if (a2 == LIM2)continue;
		int L[4] = { 0,1,1,2 }, R[4] = { 9,8,8,7 }, P[4] = { 0,5,9,13 };
		for (int i = 1; i <= 3; i++) {
			for (int j = L[i]; j <= R[i]; j++) {
				for (int k = L[i]; k <= R[i]; k++) {
					vector<vector<char>>a4 = solve(a1, j, k, i);
					vector<tuple<char, char, char>>a5 = a3; a5.push_back(make_tuple(j, k, i));
					if (RR < JJ) { Vec[RR] = make_tuple(a4, a2 + 1, a5); RR++; }
				}
			}
		}
	}
	for (int i = 0; i < Vec.size(); i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < 10; k++) {
				get<0>(Vec[i])[j][k] *= -1;
			}
		}
	}
	sort(Vec.begin(), Vec.end());
}
int main() {
	srand((unsigned)time(NULL));
	int n; cin >> n; dp[0][0] = true;
	LIM2 = 2;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 160; j++) {
			if (dp[i][j] == false)continue;
			dp[i + 1][j + 5] = true; dp[i + 1][j + 9] = true; dp[i + 1][j + 13] = true;
		}
	}
	for (int i = 0; i < 10; i++) { vector<char>V(10, 0); S.push_back(V); }
	vector<vector<char>>START = S; int SUM = 0;
	for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++) { int SS; cin >> SS; S[i][j] = SS; SUM += S[i][j]; }
	queue<tuple<vector<vector<char>>, int, vector<tuple<char, char, char>>, int>> Q;
	vector<tuple<char, char, char>>ZERO;
	Q.push(make_tuple(S, 0, ZERO, SUM));
	zen_shori();

	while (!Q.empty()) {
		vector<vector<char>>a1 = get<0>(Q.front()); int a2 = get<1>(Q.front());
		vector<tuple<char, char, char>>a3 = get<2>(Q.front()); int a4 = get<3>(Q.front()); Q.pop();
		int L[4] = { 0,1,1,2 }, R[4] = { 9,8,8,7 }, P[4] = { 0,5,9,13 };
		for (int i = 1; i <= 3; i++) {
			int rem1 = a4 - P[i], rem2 = n - (a2 + 1); bool OK = true;
			if (dp[rem2][rem1] == false)OK = false;
			if (OK == false)continue;
			int LIM = 0; if (a3.size() >= 1) LIM = get<0>(a3[a3.size() - 1]) * 10 + get<1>(a3[a3.size() - 1]);
			for (int j = L[i]; j <= R[i]; j++) {
				for (int k = L[i]; k <= R[i]; k++) {
					int DD = j * 10 + k;
					if (DD < LIM) continue;
					vector<vector<char>>G = solve(a1, j, k, i);
					vector<tuple<char, char, char>>H = a3;
					if (hantei(G) == false)continue;
					H.push_back(make_tuple(j, k, i));
					if (G == START && a2 + 1 == n) {
						for (int j = 0; j < H.size(); j++) {
							cout << (int)get<1>(H[j]) << ' ' << (int)get<0>(H[j]) << ' ' << (int)get<2>(H[j]) << endl;
						}
						goto E;
					}
					if (a2 + 1 >= n - LIM2) {
						int P = lower_bound(Vec.begin(), Vec.end(), make_tuple(G, 0, ZERO)) - Vec.begin();
						if (P < Vec.size() && get<0>(Vec[P]) == G) {
							for (int j = 0; j < H.size(); j++) {
								cout << (int)get<1>(H[j]) << ' ' << (int)get<0>(H[j]) << ' ' << (int)get<2>(H[j]) << endl;
							}
							vector<tuple<char, char, char>>J = get<2>(Vec[P]);
							for (int j = 0; j < J.size(); j++) {
								cout << (int)get<1>(J[j]) << ' ' << (int)get<0>(J[j]) << ' ' << (int)get<2>(J[j]) << endl;
							}
							goto E;
						}
					}
					Q.push(make_tuple(G, a2 + 1, H, a4 - P[i]));
				}
			}
		}
	}
E:;
	return 0;
}

Compiler output:
a.cc: In function 'bool hantei(std::vector<std::vector<char> >)':
a.cc:67:33: error: 'n' was not declared in this scope
   67 |         if (rand() % 10 == 0 && n == 12)return false;
      |                                 ^