题解 P1312 【Mayan游戏】
这题卡了快一星期了（万恶的晚自习+周末补课）
不知不觉敲了200多行...
当然其实只需要考虑3种状况
向右移： 右边是空的/不是空的
向左移： 左边是空的 （因为优先向右移所以不需要考虑不是空的的情况）
动态数组存答案方便一些
（话说把每一步都分成一个函数也许比较好理解吧....）
还有对于以下所有的 a[x][y] ：x表示行（1~7） y表示列（1~5）
#include<iostream>
#include<cstdlib> //exit(0); 使用此库（否则提交过不去）
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
struct data{
int x1,y1,dir;
};
int a[10][10],b[10],n;
int co2;
bool tag; 判断交换进行后是否发生消除
vector <data> h;
void redraw1(int i,int j)
{
int x=j,y=i,dis=0;
while(a[x][y]==co2) {y++; dis++;}
y=i-1;
while(a[x][y]==co2) {y--; dis++;}
y++;
if(dis>=3)
{
tag=1;
while(a[x][y]==co2)
{
a[x][y]=-1; y++;
}
}
}
void redraw2(int i,int j) //以上两个函数其实都是为了针对第8个点....因为这里有十字消除的情况
{
int x=j,y=i,dis=0;
while(a[x][y]==co2) {x++; dis++;}
x=j-1;
while(a[x][y]==co2) {x--; dis++;}
x++;
if(dis>=3)
{
tag=1;
while(a[x][y]==co2)
{
a[x][y]=-1; x++;
}
}
}
void draw(int i,int j) 查找是否有可以消除的
{
int x=j,y=i,dis=0; bool flag=0;
while(a[x][y]==co2) {y++; dis++;}
y=i-1;
while(a[x][y]==co2) {y--; dis++;}
y++;
if(dis>=3)
{
tag=1; flag=1;
while(a[x][y]==co2)
{
redraw2(y,x);
a[x][y]=-1; y++;
}
} //以上为横向消除判断
x=j; y=i; dis=0; a[x][y]=co2;
while(a[x][y]==co2) {x++; dis++;}
x=j-1;
while(a[x][y]==co2) {x--; dis++;}
x++;
if(dis>=3)
{
while(a[x][y]==co2)
{
redraw1(y,x);
a[x][y]=-1; x++;
}
flag=1; tag=1;
} //以上为纵向消除判断
if(flag) a[j][i]=-1; //由于当前点为横向纵向的共用点，所以特殊判断
}
void turnd() //消除方块后要把空位补上
{
bool fla;
for(int i=1;i<=5;i++)
{
fla=0;
for(int j=7;j>=1;j--)
{
if(a[j][i]==0) break;
if(a[j][i]>0)
{
fla=1; b[i]=j;
}
if(a[j][i]==-1)
{
int z=j;
while(a[z][i]==-1) z--;
a[j][i]=a[z][i];
if(a[z][i])
{
b[i]=j; fla=1;
a[z][i]=-1;
}
}
}
if(!fla) b[i]=8; //具体见下
}
}
inline void findd() //重复查找（具体见下）
{
tag=0;
for(int i=1;i<=5;i++)
for(int j=7;j>=1;j--)
{
if(a[j][i]==0) break;
co2=a[j][i];
draw(i,j);
}
}
inline int pd() //b[i]为高度数组，储存本列方块的(7-高度+1），如果==8说明此列为空
{
for(int i=1;i<=5;i++) if(b[i]!=8) return 0;
return 1;
}
void dfs(int w)
{
if(w==n)
{
if(pd())
{
int len=h.size();
for(int i=0;i<len;i++) printf("%d %d %d\n",h[i].x1-1,7-h[i].y1,h[i].dir); //题目要求从左下角（0,0）开始，而我的程序是从左上角（1,1）开始【为了好理解】，所以需要做一些小修改
exit(0); //直接结束整个程序
}
return ;
}
int i,j,k1,k2,q1[8][6],q2[6];
for(i=1;i<=5;i++)
{
q2[i]=b[i];
for(j=1;j<=7;j++) q1[j][i]=a[j][i];
} //临时数组
for(i=1;i<=5;i++)
{
for(j=7;j>=1;j--) //根据最小字典序
{
if(a[j][i]<=0) continue;
if(i+1<=5&&a[j][i]!=a[j][i+1]&&a[j][i+1]!=-1) //向右移
{
tag=0;
if(a[j][i+1]>0)
{
swap(a[j][i],a[j][i+1]);
co2=a[j][i]; draw(i,j);
co2=a[j][i+1]; draw(i+1,j);
}
else
{
b[i+1]--; co2=a[j][i]; a[b[i+1]][i+1]=a[j][i];
for(int u1=j;u1>=1;u1--)
{
if(a[u1][i]==0) break;
a[u1][i]=a[u1-1][i];
}
b[i]++; draw(i+1,b[i+1]);
for(int u1=j;u1>=1;u1--)
{
if(a[u1][i]<=0) break;
co2=a[u1][i]; draw(i,u1);
}
}
while(tag) {turnd(); findd();} //如果有可以消除的则循环消除直到无法消除，下同
h.push_back((data){i,j,1}); //储存答案，下同
dfs(w+1);
h.pop_back();
for(k1=1;k1<=5;k1++)
{
b[k1]=q2[k1];
for(k2=1;k2<=7;k2++) a[k2][k1]=q1[k2][k1];
} //回溯，下同
}
if(i-1>=1&&a[j][i-1]==0&&b[i]<b[i-1]) //向左移
{
b[i-1]--; co2=a[j][i]; a[b[i-1]][i-1]=a[j][i];
for(int u1=j;u1>=1;u1--)
{
if(a[u1][i]==0) break;
a[u1][i]=a[u1-1][i];
}
b[i]++; draw(i-1,b[i-1]);
for(int u1=j;u1>=1;u1--)
{
if(a[u1][i]<=0) break;
co2=a[u1][i]; draw(i,u1);
}
while(tag) {turnd(); findd();}
h.push_back((data){i,j,-1});
dfs(w+1);
h.pop_back();
for(k1=1;k1<=5;k1++)
{
b[k1]=q2[k1];
for(k2=1;k2<=7;k2++) a[k2][k1]=q1[k2][k1];
}
}
}
}
}
int main()
{
scanf("%d",&n);
int i,j,q;
for(i=1;i<=5;i++)
{
q=1;j=7;
while(q)
{
scanf("%d",&q);
a[j][i]=q;
if(q) j--;
}
b[i]=j+1;
} //读入数据时直接改成纵向
dfs(0);
printf("-1");
return 0;
}