P1312 Mayan游戏
无秒
2020-05-16 20:57:29
这题是个非常简单~~（难的要死）~~的搜索。真的没啥技巧（讲透了就那个简单的剪枝），然后，就靠着码力刚了……qwq
这个思路稍微的讲一下（思路简单，代码……）：就是搜索，没啥别的。
首先，明确搜索包含的东西：其实就是搜到第x步，只要传这个就行，x>n（完成需要步数）时肯定return了。
还有要砍的就是，要往一个方向搜（就像之前的小木棍，就直接接着上一个搜，否则就会有很多种（组合的庞大数量，我就不用讲了吧……））。
然后要加上几个函数（就是方便一点，而且这非常有利于思路的清晰）（简单的就不讲详细了）：
（感谢消灭星星）首先，判断一下最后是否图里面还有没有星星；其次，就是消除星星后掉下星星；接着，消灭星星！因为它说假如是横竖3个的交集，全都要消去（差不多等于消灭星星），所以把所有的3个点标记，统一去掉就OK；最后就是交换星星，swap嘛，然后掉下来，去除相同的，再掉下来……然后，dfs就直接OK了……
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[6][8],ans[6][4],temp[6][6][8];
int n;
bool c[6][8];
inline void read(int &x)
{
x=0;
int f=0;
char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void write(int x)
{
char s[30];
int top=0;
while(x) s[++top]=x%10,x/=10;
if(!top) putchar('0');
else while(top) putchar(s[top--]+'0');
}
bool check()
{
for(int i=5;i>=1;i--) if(a[i][1]) return false;
return true;
}
void copy(int x){
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
temp[x][i][j]=a[i][j];
}
void fall()
{
int x;
for(int i=1;i<=5;i++){
x=0;
for(int j=1;j<=7;j++){
if(!a[i][j]) x++;
else{
if(!x) continue;
a[i][j-x]=a[i][j];
a[i][j]=0;
}
}
}
}
bool clear()
{
bool flag=false;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
{
if(i>1&&i<5&&a[i][j]==a[i-1][j]&&a[i][j]==a[i+1][j]&&a[i][j])
c[i][j]=c[i-1][j]=c[i+1][j]=flag=true;
if(j>1&&j<7&&a[i][j]==a[i][j-1]&&a[i][j]==a[i][j+1]&&a[i][j])
c[i][j]=c[i][j-1]=c[i][j+1]=flag=true;
}
if(!flag) return false;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(c[i][j])
{
c[i][j]=false;
a[i][j]=0;
}
return true;
}
void move(int i,int j,int x)
{
swap(a[i][j],a[i+x][j]);
fall();
while(clear()) fall();
}
void dfs(int x)
{
if(check()){
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++)
printf("%d ",ans[i][j]);
if(i!=n) printf("\n");
}
exit(0);
}
if(x>n) return;
copy(x);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
//if(a[i][j])
{
if(i<5&&a[i][j]!=a[i+1][j]){
move(i,j,1);
ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
a[i][j]=temp[x][i][j];
ans[x][1]=ans[x][2]=ans[x][3]=-1;
}
/*if(i>1&&a[i-1][j]==0){
move(i,j,-1);
ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
a[i][j]=temp[x][i][j];
ans[x][1]=ans[x][2]=ans[x][3]=-1;
}*/
}
}
int main()
{
read(n);
for(int i=1;i<=5;i++)
for(int j=1;j<=8;j++)
{
read(a[i][j]);
if(a[i][j]==0) break;
}
dfs(1);
printf("-1");
return 0;
}
```