NOIP 2011 Mayan游戏 大暴搜

2019-05-08 07:23:40来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接:https://www.luogu.org/problemnew/show/P1312

我的第一篇题解!!

当然感谢ZAGER 的提示,他的链接https://www.cnblogs.com/ZAGER/p/9535526.html

 

这道题是一个大暴搜,真实考验了我的代码能力……

写函数是个好习惯,思路清晰明了。

分步骤

定义map[i][j]表示当前地图的情况,last[x][i][j]表示第x步时地图原貌,ans[x][i]记录第x步时的操作

 

check()检查是否被消完,当然根据规则只要检查最下面一行是否都被消完即可;

bool check()
{
    for(int i=1;i<=5;i++)
    {
        if(map[i][1]) return 0;
    }
    return 1;
}

update()进行掉落过程,我们从下往上搜,记录当前map有值的时候其下面有几个空行

void update()//掉落过程 
{
    for(int i=1;i<=5;i++)
    {
        int down=0;
        for(int j=1;j<=7;j++)
        {
            if(!map[i][j]) down++;
            else
            {
                if(!down) continue;
                map[i][j-down]=map[i][j];
                map[i][j]=0;
            }
        }
    }
}

重点在这(对于我来说)

 

转换移动的操作,没好好看题,移动的时候不一定只和其他方块互换,也可以拖到悬空,然后掉落,所以互换后要检查掉落情况

void move(int x,int y,int z)//转换移动 
{
    int mem=map[x][y];
    map[x][y]=map[x+z][y];
    map[x+z][y]=mem;
    update();
    while(remove()) update();//被消除后进行掉落 
}

remove()用来进行消除过程。为了满足条件图5情况,我们先记录在进行消除。

int remove()//消除过程 
{
    bool flag=0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j])
            {
                xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1;
            }
            if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1])
            {
                xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1;
            }
        }
    }//先记录再消除,满足图五情况 
    if(!flag) return 0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(xx[i][j])
            {
                map[i][j]=0;
                xx[i][j]=0;
            }
        }
    }
    return 1;
}

 

还有几个无关紧要(也很重要)的小函数,代码里有注解

还有一个重要的剪枝,就是“向左的时候如果左方并非是空,则跳过(否则可以选择其左侧方块右移,这样字典序更小)”;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int map[10][10],last[10][10][10],ans[10][5];//map当前地图,;last第几步移动前的地图;ans是前为步数,后为答案 
int xx[10][10];
bool check()
{
    for(int i=1;i<=5;i++)
    {
        if(map[i][1]) return 0;
    }
    return 1;
}

void  memory(int x)
{
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            last[x][i][j]=map[i][j];//记录第x步时地图的原貌 
        }
    }
}

void update()//掉落过程 
{
    for(int i=1;i<=5;i++)
    {
        int down=0;
        for(int j=1;j<=7;j++)
        {
            if(!map[i][j]) down++;
            else
            {
                if(!down) continue;
                map[i][j-down]=map[i][j];
                map[i][j]=0;
            }
        }
    }
}

int remove()//消除过程 
{
    bool flag=0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j])
            {
                xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1;
            }
            if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1])
            {
                xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1;
            }
        }
    }//先记录再消除,满足图五情况 
    if(!flag) return 0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(xx[i][j])
            {
                map[i][j]=0;
                xx[i][j]=0;
            }
        }
    }
    return 1;
}
void move(int x,int y,int z)//转换移动 
{
    int mem=map[x][y];
    map[x][y]=map[x+z][y];
    map[x+z][y]=mem;
    update();
    while(remove()) update();//被消除后进行掉落 
}

void recover(int x)
{
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            map[i][j]=last[x][i][j];
        }
    }
    ans[x][1]=0;ans[x][2]=0;ans[x][3]=0;
}
void dfs(int x)
{
    if(check())
    {
        for(int i=1;i<=n;i++)
        {
            if(i!=1) printf("\n");
            for(int j=1;j<=3;j++)
            {
                printf("%d ",ans[i][j]);
            }
        }
        exit(0);
    }
    if(x==n+1) return ;
    memory(x);
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(map[i][j])
            {
                if(i<=6&&map[i][j]!=map[i+1][j])
                {
                    move(i,j,1);
                    ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
                    dfs(x+1);
                    recover(x);//恢复原地图和ans 
                }
            }
            if(i>=2&&(!map[i-1][j]))
            {
                move(i,j,-1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
                dfs(x+1);
                recover(x);
            }
        }
    }

    
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=8;j++)
        {
            int x;
            scanf("%d",&x);
            if(x==0) break;
            map[i][j]=x;
        }
    }
    dfs(1);//从第一步开始搜
    printf("-1\n");
    return 0;
}

 


原文链接:https://www.cnblogs.com/WHFF521/p/10827094.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++线性表通过结构体实现操作和结构体字符串快速排序和shell排序

下一篇:图论2——拓扑排序