题解：P1312 [NOIP2011 提高组] Mayan 游戏

#include<iostream>
#include<cstring>
using namespace std;
struct Node{
	int x, y, op;
};
Node b[10]; 
int a[10][10];
int n;
inline void down(){
	for (int i = 1; i <= 5; i++){
		int sz = 0;
		for (int j = 1; j <= 7; j++)
			if (a[i][j]) a[i][++sz] = a[i][j];
		for (int j = sz + 1; j <= 7; j++) a[i][j] = 0;
	}
}
inline bool del(){
	int t[10][10];
	memcpy(t, a, sizeof(a));
	bool flag = false;
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (!a[i][j]) continue;
			if (a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j]){
				t[i][j] = t[i - 1][j] = t[i + 1][j] = 0;
				flag = true;
			}
			if (a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1]){
				t[i][j] = t[i][j - 1] = t[i][j + 1] = 0;
				flag = true;
			}
		}
	}
	memcpy(a, t, sizeof(t));
	return flag;
}
inline void dfs(int step){
	down();
	while (del()) down();
	if (step > n){
		for (int i = 1; i <= 5; i++)
			if (a[i][1]) return;
		for (int i = 1; i <= n; i++)
			cout << b[i].x - 1 << " " << b[i].y - 1 << " " << b[i].op << endl;
		exit(0);
	}
	int t[10][10];
	memcpy(t, a, sizeof(a));
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (a[i][j] == 0) break;
			if (i < 5){
				swap(a[i][j], a[i + 1][j]);
				b[step] = {i, j, 1};
				dfs(step + 1);
				memcpy(a, t, sizeof(t));
			}
			if (i > 1 && a[i - 1][j] == 0){
				swap(a[i][j], a[i - 1][j]);
				b[step] = {i, j, -1};
				dfs(step + 1);
				memcpy(a, t, sizeof(t));
			}
		}
	}
}
int main(){
	cin >> n;
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 8; j++){
			int x;
			cin >> x;
			if (x == 0) break;
			a[i][j] = x;
		}
	}	
	dfs(1);
	cout << -1 << endl;
	return 0;
}