题解 P1312 【Mayan游戏】
redegg
·
·
题解
这个题告诉我们模块化是多么的重要，有清晰思路的代码比天马行空的反人类高智商代码好很多。
建议边写边调，写完一个模块就去测试这个模块，免得全部堆到最后心烦意乱。
剩下的，就是我都没想到我会A了这题，这个复杂度是比较玄学的。
码农工业题，全靠rp
那么说一下这题的思路吧，我们可以分成三个大模块:
消消乐（kill？）模块，重力(fall?)模块，搜索(dfs)模块。（我这英语绝了！）
对于消消乐模块，可以分成行和列分别处理，每行每列一旦超过3个相同的，就标记一下，最后把标记的点删除为0。
对于重力模块，直接暴力往下冒泡地丢就好了。
对于搜索模块，用stl的map进行记忆化，剪掉同一步数的同一状态，还有步数超限的。
然后找到了全图为0就输出如何搜过来的就行了。
没找到输出是-1。
由于是在学校模拟的时候睡了一觉写的题，手感极好，注释就懒得删了，毕竟是一个调试过程。
```
#include <bits/stdc++.h>
using namespace std;
int n;
struct ha
{
int m[10][10],ss;
bool operator == (const ha aa)const
{
if(ss!=aa.ss)return false;
for(int i=1; i<=7; i++)
{
for(int j=1; j<=5; j++)
{
if(aa.m[i][j]!=m[i][j])
return false;
}
}
return true;
}
bool operator < (const ha aa)const
{
for(int i=1; i<=7; i++)
{
for(int j=1; j<=5; j++)
{
if(aa.m[i][j]==m[i][j])
continue;
return m[i][j]<aa.m[i][j];
}
}
if(ss<aa.ss)return true;
return false;
}
} a[10];
map<ha,bool> b;
void draw(int id)
{
cout<<endl;
for(int i=1;i<=7;i++)
{
for(int j=1;j<=5;j++)
cout<<a[id].m[i][j]<<" ";
cout<<endl;
}
}
void kill(int id)
{
bool k[10][10];
memset(k,0,sizeof(k));
for(int i=1; i<=7; i++)
{
int last=0;
if(a[id].m[i][1]!=0)
last=1;
for(int j=2; j<=6; j++)
{
if(a[id].m[i][j]==a[id].m[i][j-1]&&a[id].m[i][j-1]!=0)
last++;
else if(a[id].m[i][j]!=a[id].m[i][j-1])
{
if(last>=3&&a[id].m[i][j-1]!=0)
{
for(int l=j-last; l<j; l++)
k[i][l]=1;
}
last=0;
if(a[id].m[i][j]!=0)
last=1;
}
}
}
//--------------------------------------------------------------//
int ll[10];
for(int j=1; j<=5; j++)
{
ll[j]=0;
if(a[id].m[1][j]!=0)
ll[j]=1;
}
for(int i=2; i<=8; i++)
{
for(int j=1; j<=5; j++)
{
if(a[id].m[i][j]==a[id].m[i-1][j]&&a[id].m[i-1][j]!=0)
{
ll[j]++;
}
else if(a[id].m[i][j]!=a[id].m[i-1][j])
{
if(ll[j]>=3&&a[id].m[i-1][j]!=0)
{
for(int l=i-ll[j]; l<i; l++)
k[l][j]=1;
}
ll[j]=0;
if(a[id].m[i][j]!=0)
ll[j]=1;
}
}
}
//--------------------------------------------------------------//
for(int i=1; i<=7; i++)
{
for(int j=1; j<=5; j++)
{
if(k[i][j])
a[id].m[i][j]=0;
}
}
}
bool fall(int id)
{
bool op=0;
while(1)
{
bool ok=1;
for(int i=6; i>=1; i--)
{
for(int j=1; j<=5; j++)
{
if(a[id].m[i+1][j]==0&&a[id].m[i][j]!=0)
{
op=1;
ok=0;
swap(a[id].m[i+1][j],a[id].m[i][j]);
}
}
}
if(ok)
break;
}
return op;
}
void cck(int id)
{
while(1)
{
//printf("\n");
kill(id);
bool pan=fall(id);
if(pan==0)
break;
}
}
int anx[10];
int any[10];
int ank[10];
void fuzhi(int step)
{
int nw=step+1;
a[step].ss=nw;
memset(a[nw].m,0,sizeof(a[nw].m));
for(int i=1;i<=7;i++)
{
for(int j=1;j<=5;j++)
{
a[nw].m[i][j]=a[step].m[i][j];
}
}
}
int z[10]={1,-1};
bool win(int id)
{
for(int i =1;i<=7;i++)
{
for(int j=1;j<=5;j++)
{
if(a[id].m[i][j]!=0)
return false;
}
}
return true;
}
void dfs(int step)
{
//cout<<" "<<step<<endl;
//draw(step);
//system("pause");
if(win(step)&&step==n)
{
for(int i=2;i<=step;i++)
{
printf("%d %d %d\n",any[i]-1,7-anx[i],ank[i]);
}
exit(0);
}
if(step==n)
return ;
for(int j=1;j<=5;j++)
{
for(int i=7;i>=1;i--)
{
if(a[step].m[i][j]==0)continue;
for(int l=0;l<=1;l++)
{
int nx=j+z[l];
if(nx>=1&&nx<=5)
{
fuzhi(step);
swap(a[step+1].m[i][nx],a[step+1].m[i][j]);
//cout<<i<<" "<<j<<" "<<z[l]<<endl;
//draw(step+1);
//cout<<b[a[step+1]]<<endl;
cck(step+1);
if(b[a[step+1]]==1)
{
//cout<<"go!"<<endl;
continue;
}
//if(a[step].m[6][4]==3)
//{
//draw(step);
//draw(step+1);
//system("pause");
//}
b[a[step+1]]=1;
anx[step+1]=i;
any[step+1]=j;
ank[step+1]=z[l];
cck(step+1);
dfs(step+1);
}
}
}
}
}
int main()
{
//freopen("mayan.in","r",stdin);
//freopen("mayan.out","w",stdout);
scanf("%d",&n);
n+=1;
memset(a[1].m,0,sizeof(a[1].m));
for(int i=1;i<=5;i++)
{
int op=7;
while(1)
{
int x;
scanf("%d",&x);
if(x==0)
break;
a[1].m[op][i]=x;
op--;
}
}
a[1].ss=1;
/*
for(int i=1;i<=7;i++)
{
for(int j=1;j<=5;j++)
scanf("%d",&a[1].m[i][j]);
}*/
//draw(1);
b[a[1]]=1;
//cout<<b[a[1]]<<endl;
dfs(1);
printf("-1\n");
return 0;
}
```