题解 P1312 【Mayan游戏】

varvar · 2016-02-20 08:34:12 · 题解

/*
此题的剪枝，对于每个点，不进行左移。
另外检查掉落时，不要一个一个掉，一次性掉到底。
注意移动完后可能会有多次消方块。 
*/

#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct id
{
    int xx,yy,gg;
};
id ans[100];
int map[100][10][10],n; 

bool pd(int x)//判断map[x] 
{
    for (int i=1;i<=7;i++)
    for (int j=1;j<=5;j++)
    if (map[x][i][j]!=0) return false;
    return true;
}

void check(int x)//对map[X]中检查掉落 
{
    for (int i=2;i<=7;i++)
    for (int j=1;j<=5;j++)    
    if (map[x][i][j]!=0 && map[x][i-1][j]==0)
    {
        int t=i;
        while (map[x][t-1][j]==0 && t-1>0) t--;
        map[x][t][j]=map[x][i][j];
        map[x][i][j]=0;
    }
}

bool xfk(int x)//消方块，x表示消哪个map的方块 
{
    bool f[10][10],flag=false;//flag表示是否有方块消除过 
    //用一个标记数组，对map上每个点进行扩展，发现可扩展数大于等于3，就标记，最后统一赋值为0 
    for (int i=1;i<=7;i++)
    for (int j=1;j<=5;j++)
    f[i][j]=false;
    for (int i=1;i<=7;i++)
    for (int j=1;j<=5;j++)
    if (map[x][i][j]!=0)
    {
        int t1=1,t2=1,t3=1,t4=1;
        while (map[x][i][j+t1]==map[x][i][j]) t1++;
        while (map[x][i][j-t2]==map[x][i][j]) t2++;
        while (map[x][i+t3][j]==map[x][i][j]) t3++;
        while (map[x][i-t4][j]==map[x][i][j]) t4++;
        if (t1+t2>3 || t3+t4>3) f[i][j]=true;
    }
    for (int i=1;i<=7;i++)
    for (int j=1;j<=5;j++)
    if (f[i][j]) map[x][i][j]=0,flag=true;
    check(x);
    return flag;
}

void change(int x,int y,int x1,int y1,int x2,int y2)
//把map[x][x1][y1]和map[x][x2][y2]交换，并且存到map[y]中 
{
     for (int i=1;i<=7;i++)
    for (int j=1;j<=5;j++)
    map[y][i][j]=map[x][i][j];
    int t=map[y][x1][y1];
    map[y][x1][y1]=map[y][x2][y2];
    map[y][x2][y2]=t;
    check(y);
    while (xfk(y));
}

void dfs(int x,int y)
{
    if (x==n && pd(y)) 
    {
        for (int i=1;i<=n;i++)
        printf("%d %d %d\n",ans[i].yy-1,ans[i].xx-1,ans[i].gg);
        exit(0);
    }
    if (x==n) return;
    for (int j=1;j<=5;j++)
    for (int i=1;i<=7;i++)
    if (map[y][i][j]!=0)
    {
        if (j+1<=5)//右移 
        {
            if (map[y][i][j+1]==0) change(y,y+1,i,j,i,j+1);
            else change(y,y+1,i,j,i,j+1);
            ans[x+1].xx=i;
            ans[x+1].yy=j;
            ans[x+1].gg=1;
            dfs(x+1,y+1); 
        }
        if (j-1>=1 && map[y][i][j-1]==0)//左移，只进行移动，不交换 
        {
            change(y,y+1,i,j,i,j-1);        
            ans[x+1].xx=i;
            ans[x+1].yy=j;
            ans[x+1].gg=-1;
            dfs(x+1,y+1);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=5;i++)
    {
        int j=0,t;
        scanf("%d",&t);
        while (t!=0) 
        {
            j++;
            map[0][i][j]=t;
            scanf("%d",&t);
        }
    }
    for (int i=1;i<=5;i++)
    for (int j=1;j<=7;j++)
    map[1][j][i]=map[0][i][j];
    dfs(0,1);    
    printf("-1");
return 0;
}