题解：P1312 [NOIP 2011 提高组] Mayan 游戏
[NOIP 2011] Mayan 游戏
这题其实挺简单的吧……。
其实比想象中的好写很多，就是烦，有很多的优化。
思路
这题的话我们可以编写很多的函数来模拟这个过程，例如下落，清理，判空等等，最后呢再利用深搜遍历左移和右移，注意两个方向的优先，一定要小心变量名不要写错，别问为什么，调了一个下午没调出来。
函数内容
empty 函数
函数功能：判断区域内是否已经被清空。
bool empty()//判断是否已经清空
{
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j])return false;
return true;
}copy 函数
函数功能：将数组
void copy(int x[10][10],int y[10][10])
{
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
y[i][j]=x[i][j];
}drop 函数
函数功能：判断区块是否掉落。
void drop()//判断掉落
{
memset(c,0,sizeof(c));
for(int i=0;i<5;i++)
for(int j=0,k=0;j<7;j++)
if(a[i][j])c[i][k++]=a[i][j];
copy(c,a);
}clear 函数
函数功能：按照横向和纵向判断区块数量，可以理解成枚举。
bool clear()
{
bool flag=false;
int xx,yy,up,dn;
for(int i=0;i<3;i++)//横向判断块数不小于 3
for(int j=0;j<7;j++)
if(a[i][j])
{
for(xx=i;xx<5&&a[xx+1][j]==a[i][j];xx++);//横向
if(xx-i+1>=3)
{
for(int k=i;k<=xx;k++)
{
up=j;dn=j;
while(up+1<7&&a[k][up+1]==a[k][j])up++;
while(dn-1>=0&&a[k][dn-1]==a[k][j])dn--;
if(up-dn+1>=3)
for(int l=dn;l<=up;l++)
a[k][l]=0;
else a[k][j]=0;
}
flag=true;
}
}
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)//纵向判断块数不小于 3
if(a[i][j])
{
for(yy=j;yy+1<7&&a[i][yy+1]==a[i][j];yy++);//纵向
if(yy-j+1>=3)
{
for(int k=j;k<=yy;k++)
{
up=i;dn=i;
while(up+1<7&&a[up+1][k]==a[i][k])up++;
while(dn-1>=0&&a[dn-1][k]==a[i][k])dn--;
if(up-dn+1>=3)
for(int l=dn;l<=up;l++)
a[l][k]=0;
else a[i][k]=0;
}
flag=true;
}
}
return flag;
}深搜就不用说啦，应该有基础的人都知道吧，但是唯一的难点就是回溯，我们需要用几个辅助的容器，把数据复制，这就是前面 copy 函数的作用了。
主函数就更不用说了吧，直接输入然后调用函数就好了。
放一下完整的代码，调了好久啊啊啊啊啊啊啊
代码
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[10][10],c[10][10],sum[20];
struct node{int x,y,dir;}ans[10];
bool empty()//判断是否已经清空
{
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j])return false;
return true;
}
void copy(int x[10][10],int y[10][10])
{
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
y[i][j]=x[i][j];
}
void drop()//判断掉落
{
memset(c,0,sizeof(c));
for(int i=0;i<5;i++)
for(int j=0,k=0;j<7;j++)
if(a[i][j])c[i][k++]=a[i][j];
copy(c,a);
}
bool clear()
{
bool flag=false;
int xx,yy,up,dn;
for(int i=0;i<3;i++)//横向判断块数不小于3
for(int j=0;j<7;j++)
if(a[i][j])
{
for(xx=i;xx<5&&a[xx+1][j]==a[i][j];xx++);//横向
if(xx-i+1>=3)
{
for(int k=i;k<=xx;k++)
{
up=j;dn=j;
while(up+1<7&&a[k][up+1]==a[k][j])up++;
while(dn-1>=0&&a[k][dn-1]==a[k][j])dn--;
if(up-dn+1>=3)
for(int l=dn;l<=up;l++)
a[k][l]=0;
else a[k][j]=0;
}
flag=true;
}
}
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)//纵向判断块数不小于3
if(a[i][j])
{
for(yy=j;yy+1<7&&a[i][yy+1]==a[i][j];yy++);//纵向
if(yy-j+1>=3)
{
for(int k=j;k<=yy;k++)
{
up=i;dn=i;
while(up+1<7&&a[up+1][k]==a[i][k])up++;
while(dn-1>=0&&a[dn-1][k]==a[i][k])dn--;
if(up-dn+1>=3)
for(int l=dn;l<=up;l++)
a[l][k]=0;
else a[i][k]=0;
}
flag=true;
}
}
return flag;
}
void dfs(int step)
{
if(step>n)//达到步数
{
if(empty())
{
for(int i=1;i<=n;i++)
if(ans[i].dir)printf("%d %d -1\n",ans[i].x+1,ans[i].y);
else printf("%d %d 1\n",ans[i].x,ans[i].y);
exit(0);
}
return;
}
memset(sum,0,sizeof(sum));
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
sum[a[i][j]]++;
for(int i=1;i<=10;i++)//若当前状态里同种颜色方块数量不足3，直接返回
if(sum[i]>0&&sum[i]<3)return;
for(int i=0;i<4;i++)//右移优先于左移
for(int j=0;j<7;j++)
if(a[i][j]!=a[i+1][j])//若颜色相同则没有移动的必要
{
int b[10][10];
copy(a,b);
ans[step]=(node){i,j,!a[i][j]};//注意判断当前方块是否为空
swap(a[i][j],a[i+1][j]);
drop();
while(clear())drop();
dfs(step+1);
copy(b,a);
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<5;i++)
for(int j=0;;j++)
{
scanf("%d",&a[i][j]);
if(!a[i][j])break;
}
dfs(1);
printf("-1\n");
return 0;//好习惯
}补充一下 Hack 数据
一开始被 Hack 掉了，这个数据主要就是一个关于无效交换的特判，在往右边时不应该多加不同才交换。