这道题的搜索思路并不难,比较复杂的是move的处理。 在move函数中,我们要先使方块下落,然后判断是否可以消除,进行消除后再使方块下落,再消除... 因此我们用一个while循环,进行下落→标记→消除,如果当前不能消除,则move结束。
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int g[5][7],bg[5][5][7];
int cnt[11],bcnt[5][11];
struct path{
int x,y,c;
};
path p[10];
bool st[10][10];
void move(int x,int y,int nx)
{
swap(g[x][y],g[nx][y]);
while(1)
{
bool flag=1;
for(int i=0;i<5;i++)
{
int k=0;
for(int j=0;j<7;j++)
{
if(g[i][j]) g[i][k++]=g[i][j];
}
while(k<7) g[i][k++]=0;
}
memset(st,0,sizeof(st));
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(g[i][j])
{
int l=i,r=i;
while(l-1>=0&&g[l-1][j]==g[i][j]) l--;
while(r+1<5&&g[r+1][j]==g[i][j]) r++;
if(r-l+1>=3)
{
st[i][j]=1;
flag=0;
}
else
{
l=j,r=j;
while(l-1>=0&&g[i][l-1]==g[i][j]) l--;
while(r+1<7&&g[i][r+1]==g[i][j]) r++;
if(r-l+1>=3)
{
st[i][j]=1;
flag=0;
}
}
}
if(flag) break;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(st[i][j])
{
cnt[0]--;
cnt[g[i][j]]--;
g[i][j]=0;
}
}
}
bool dfs(int u)
{
if(u==n) return cnt[0]==0;
for(int i=1;i<=10;i++)
if(cnt[i]==1||cnt[i]==2)
return false;
memcpy(bg[u],g,sizeof(g));
memcpy(bcnt[u],cnt,sizeof(cnt));
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(g[i][j])
{
int nx=i+1;
if(nx<5)
{
p[u]={i,j,1};
move(i,j,nx);
if(dfs(u+1)) return true;
memcpy(g,bg[u],sizeof(g));
memcpy(cnt,bcnt[u],sizeof(cnt));
}
nx=i-1;
if(nx>=0&&!g[nx][j])
{
p[u]={i,j,-1};
move(i,j,nx);
if(dfs(u+1)) return true;
memcpy(g,bg[u],sizeof(g));
memcpy(cnt,bcnt[u],sizeof(cnt));
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<5;i++)
{
int j=0,x;
while(cin>>x&&x!=0)
{
g[i][j]=x;
cnt[0]++;
cnt[x]++;
j++;
}
}
if(dfs(0))
for(int i=0;i<n;i++)
cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].c<<endl;
else cout<<-1<<endl;
}