题解 P1312 【Mayan游戏】

csyakuoi · 2018-05-04 16:38:41 · 题解

只要肯去码此题，就一定能AC

所以P2482(猪国杀)也一样

剪枝原则：

1，交换两个相同颜色的块没有意义。

2，如果一种颜色的块数量为1或2，则当前局面无解。

3，因为要求字典序最小的解，所以一个块仅当左边为空时尝试左移。

本蒟蒻写了164行，最慢的点912ms。

代码（有注释）：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 5
#define M 7

int maxstep,chess[N][M];
int count[11];
int answer[5][3];

void init(void)     //读入
{
    memset(chess,0,sizeof(chess));
    scanf("%d",&maxstep);
    for(int i=0;i<N;i++){
        int j=0,x;
        scanf("%d",&x);
        while(x!=0){
            chess[i][j]=x;
            j++;
            scanf("%d",&x);
        }
    }
    return;
}

void printchess(void)       //调试用
{
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            printf("%d ",chess[i][j]);
        putchar('\n');
    }
    return;
}

void fall(void)     //清除后方块下落
{
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            if(chess[i][j]!=0)
                continue;
            int k;
            for(k=j+1;k<M;k++)
                if(chess[i][k]!=0){
                    chess[i][j]=chess[i][k];
                    chess[i][k]=0;
                    break;
                }
            if(k==M)
                break;
        }
    return;
}

void printans(void)     //输出
{
    for(int i=0;i<maxstep;i++)
        printf("%d %d %d\n",answer[i][0],answer[i][1],answer[i][2]);
    return;
}

bool clear(void)        //清除棋盘
{
    bool empty[N][M];
    memset(empty,0,sizeof(empty));
    for(int i=0;i<3;i++)
        for(int j=0;j<M;j++)
            if(chess[i][j]!=0 && chess[i][j]==chess[i+1][j] && chess[i+1][j]==chess[i+2][j])
                empty[i][j]=empty[i+1][j]=empty[i+2][j]=1;

    for(int i=0;i<5;i++)
        for(int j=0;j<N;j++)
            if(chess[i][j]!=0 && chess[i][j]==chess[i][j+1] && chess[i][j+1]==chess[i][j+2])
                empty[i][j]=empty[i][j+1]=empty[i][j+2]=1;

    int res=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(empty[i][j]){
                chess[i][j]=0;
                res=1;
            }
    return res;
}

bool isempty(void)      // 判断棋盘是否为空
{
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(chess[i][j]!=0)
                return 0;
    return 1;
}

bool judge(void)        //判断是否有一种颜色的块数量为1或2
{
    memset(count,0,sizeof(count));
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            count[chess[i][j]]++;
    for(int i=1;i<=10;i++)
        if(count[i]==1||count[i]==2)
            return 0;
    return 1;
}

bool dfs(int step)      //搜索
{
    if(isempty()){      //发现一组解
        printans();
        return 1;
    }
    if(step>=maxstep || judge()==0)     //剪枝与结束条件
        return 0;

    int now[N][M];      //中间状态
    for(int i=0;i<N;i++)        //复制棋盘
        for(int j=0;j<M;j++)
            now[i][j]=chess[i][j];

    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){       //枚举每一个方块
            if(i!=N-1 && chess[i][j]!=0 && chess[i][j]!=chess[i+1][j]){
                int t=chess[i][j];  chess[i][j]=chess[i+1][j];  chess[i+1][j]=t;
                answer[step][0]=i;  answer[step][1]=j;  answer[step][2]=1;
                fall();
                while(clear())
                    fall();
                if(dfs(step+1))
                    return 1;
            }       //右移

            for(int k1=0;k1<N;k1++)
                for(int k2=0;k2<M;k2++)
                    chess[k1][k2]=now[k1][k2];

            if(i!=0 && chess[i][j]!=0 && chess[i-1][j]==0){
                int t=chess[i][j];  chess[i][j]=chess[i-1][j];  chess[i-1][j]=t;
                answer[step][0]=i;  answer[step][1]=j;  answer[step][2]=-1;
                fall();
                while(clear())
                    fall();
                if(dfs(step+1))
                    return 1;
            }       //左移

            for(int k1=0;k1<N;k1++)     //复制回来
                for(int k2=0;k2<M;k2++)
                    chess[k1][k2]=now[k1][k2];
        }
    return 0;
}

int main(void)
{
    init();
    //clear();
    //fall();
    //printchess();
    if(dfs(0)==0)
        printf("-1");
    return 0;
}