题解 P1312 【Mayan游戏】
先读懂题。题目要求模拟一个游戏的运行，并且搜索出最优解。不能dp也没啥启发式操作显然就是爆搜啊。
模拟和搜索难度不大，但模拟有很多细节。我调了好久才a掉这题。
有oop经验的我十分自然地把模拟和搜索分开，即用一个struct封装状态，这样代码能清晰不少，调试也方便。我感觉比那一大堆裸露的函数、数组复制好多了。
模拟
定义struct puzzle，要实现3个操作：移动方块，消除，检查状态。
使表示自然一些，这里我用i表示列，j表示行
为了方便操作，用数组h[]表示每列的高度，这样能减少循环的次数。
1.移动方块
需要讨论移到的位置是否为空。如果为空，将被移的方块放在移到列的顶部，处理掉落（整体往下移），然后改变2列的高度。如果非空，直接交换颜色值。
2.消除
因为是所有满足条件的方块同时消，而且3连情况复杂，这里我是开一个bool数组mark一下要消的方块。2个双重循环，分别检查横/竖方向是否有3个颜色相同，如果相同就标记一下（合并成1个在效率方便没啥提升）。最后按列，把没标记的重新堆起来，消除的要清0，记得改变高度。
重复直到不发生消除。
3.检查全清
很简单，h[0]~h[4]全为0就是全清。考虑到循环代价我没用循环。
搜索
按照题意的字典序搜就行了，没什么好说的。看清楚点，右移优先于左移。枚举要移动的方块和方向。移动操作记录在函数外的数组里，不断更新就行。但既然是爆搜，显然要剪枝。
交换两个颜色相同的方块没有意义，一般都能想到。
然后应该能注意到吧，如果把2个方块来回交换而没有发生消除，那么移动没有意义，可以剪掉（稍微复杂，但后面后更优的剪法）
细想一下，来回移动的实质是交换，而又因为是交换，所以让左边的右移等价于右边的左移，所以搜了两遍。前者比较优先，所以只需搜前者的右移。当且仅当坐标为空时才左移。这样剪是ac的关键。
register卡常是有用的，效果比较明显，但不是关键
我瞎搞就搞出524ms了，进榜第3页……
感觉color剪枝没啥效果，毕竟检查也是有代价的（我加了根本没明显提升）
其他细节
读入注意一下，如果状态数组正好是5*7大小，读入不要越界，不然会死，而且可能还不知道是怎么死的（我死在#8）
如果没有检查h是否合法，一定要确保空的格子清零清零清零！！！！
可以参考一下我的代码风格（注释基本上是在写程序时很自然地加的）
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int n;
int his[6][3];
struct puzzle {
int a[5][7],h[5]; //颜色数据和高度
void moveblock(int x,int y,int z) {
if (h[x+z]<=y) { //对应的位置为空
a[x+z][h[x+z]++]=a[x][y];
for (register int j=y+1;j<h[x];j++) {
a[x][j-1]=a[x][j];
}
h[x]--;
a[x][h[x]]=0;
} else { //对应位置有方块 直接交换
a[x+z][y]^=a[x][y];
a[x][y]^=a[x+z][y];
a[x+z][y]^=a[x][y];
}
}
bool process() { //进行消除，返回是否发生消除
bool res=false;
bool mark[5][7]={};
//纵向消除
for (register int i=0;i<5;i++) {
for (register int j=1;j<h[i]-1;j++) {
if (a[i][j-1]==a[i][j] && a[i][j]==a[i][j+1]) {
res=mark[i][j-1]=mark[i][j]=mark[i][j+1]=true;
}
}
}
//横向消除
for (register int i=1;i<4;i++) {
for (register int j=0;j<h[i];j++) {
if (a[i-1][j]==a[i][j] && a[i][j]==a[i+1][j]) {
res=mark[i-1][j]=mark[i][j]=mark[i+1][j]=true;
}
}
}
if (!res) return false; //没发生消除就不处理掉落了
//处理掉落
for (register int i=0;i<5;i++) {
int k=0; //掉落的位置
for (register int j=0;j<h[i];j++) {
if (!mark[i][j]) {
a[i][k++]=a[i][j];
if (k-1!=j) a[i][j]=0; //不是同一格
} else {
a[i][j]=0; //被消除的要清成0
}
}
h[i]=k;
}
return true;
}
inline bool allclear() {
return !(h[0] || h[1] || h[2] || h[3] || h[4]);
}
void process_ex() {
while (process());
}
};
puzzle ini;
void dfs(puzzle cur,int t) { //当前状态,已移动次数
bool clear=cur.allclear();
if (t==n) {
if (clear) { //达成
for (int i=0;i<n;i++) {
printf("%d %d %d\n",his[i][0],his[i][1],his[i][2]);
}
exit(0); //强退
}
return; //失败
}
for (register int i=0;i<5;i++) { //枚举x
for (register int j=0;j<cur.h[i];j++) { //枚举y
if (i!=4) { //可以往右移
if (cur.a[i+1][j]!=cur.a[i][j]) {
puzzle nxt=cur;
nxt.moveblock(i,j,1); //移动
his[t][0]=i, his[t][1]=j, his[t][2]=1; //历史记录
nxt.process_ex(); //处理消除
dfs(nxt,t+1);
}
}
if (i!=0) { //可以往左移
if (!cur.a[i-1][j]) { //剪枝：只有左边为0才能往左移
puzzle nxt=cur;
nxt.moveblock(i,j,-1);
his[t][0]=i, his[t][1]=j, his[t][2]=-1;
nxt.process_ex();
dfs(nxt,t+1);
}
}
}
}
}
int main() {
scanf("%d",&n);
for (int i=0;i<5;i++) {
ini.h[i]=0;
for (int &j=ini.h[i];true;j++) {
int tmp;
scanf("%d",&tmp);
if (tmp==0) break;
if (j<7) ini.a[i][j]=tmp;
}
}
dfs(ini,0);
printf("%d\n",-1);
return 0;
}