洛谷1312 Mayan游戏

@Llf0703  December 13, 2018

要不是徐妈让我做,我这辈子都不可能碰这道题的。

这是我做过的代码最长的非数据结构题,模拟题最长也就一百来行,这道题第一次原生态(包括注释和调试)交上去有214行,删掉调试输出和合并一些if后也有174行。

况且我一点优化都没加,纯种裸暴搜,加了优化不知道有多复杂。不过这题暴力能过就是了,吸氧前最大点1618ms,吸氧后774ms。

思路

整个过程可以分为 移动 --> 移动后的掉落 --> 消除 --> 消除后的掉落 --> 继续消除 --> 继续消除后的掉落 --> ...

移动

显然,相同颜色的块是不用移动的。其次,如果在中间左移右移是等价的,为了让字典序尽可能小,我们肯定尽可能选择右移。那么左移就只可能发生在当前块左边是空的情况下。

然后移动的话交换就行了,掉落是下一步的事。

移动使用 $mv(x,y,s)$ 函数,其中 $(x,y)$ 是移动的块,$s=1$ 代表右移,$s=-1$ 代表左移。$drop()$就是掉落,后面就讲。

inline void mv(int x,int y,int s) //之前已经保证没有越界
{
    swap(stat.s[x][y],stat.s[x+s][y]);
    drop();
}

消除

由于 $drop()$ 是一样的,所以把消除讲完后再讲。

消除其实就是找到连续的块打一个 $mark[x][y]=1$ 的标记就行了。这里采用dfs,如果满足条件(即连续个数>=3)那么在回溯时打上标记即可。

既然说了是裸暴搜,我用的方法自然就很暴力,直接双重循环查找起点然后作为起点往上下左右搜索就行了。

既然还要实现掉落后还要删除的问题,我就把它返回一个bool,如果还有可以删除的块,也就是 $marked>0$ 就返回true再做一遍。需要消除的地方这么写就行了:

while (update());

下面是整个消除的代码:

bool dfs_update(int x,int y,int fx,int fy,int step) //dfs标记所有可以消除的
{
    bool can;
    if (step>=3) can=1;
    else can=0;
    if (stat.s[x+fx][y+fy]==stat.s[x][y]) can=can || dfs_update(x+fx,y+fy,fx,fy,step+1);
    if (can) mark[x][y]=1;
    return can;
}

inline bool update() //消去所有可以消的方块
{
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!stat.s[i][j]) continue;
            dfs_update(i,j,0,1,1); //纵向上
            dfs_update(i,j,0,-1,1); //纵向下
            dfs_update(i,j,1,0,1); //横向右
            dfs_update(i,j,-1,0,1); //横向左
        }
    }
    int marked=0;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=7;j++)
            marked+=mark[i][j];
    drop();
    return marked;
}

掉落

两种掉落其实原理是一样的,把空格填上就行了。当然,消除后的掉落还要兼任一个把标记过的方块删掉(也就是赋值为0)的操作。虽然只有消除后掉落需要这么做,但移动后掉落反正也没有标记,统一用这个也没有任何问题。

inline void drop()
{
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!mark[i][j]) continue;
            mark[i][j]=0;
            stat.s[i][j]=0;
        }
        for (int j=1;j<=7;j++)
        {
            if (stat.s[i][j]) continue; //找到空格删除
            int cnt=0;
            for (int k=j+1;k<=7;k++)
            {
                if (!stat.s[i][k]) continue;
                stat.s[i][j+cnt]=stat.s[i][k];
                cnt++;
                stat.s[i][k]=0;
                break;
            }
        }
    }
}

检查是否清空

直接检查每一列第一个是否为0就行了。

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

整个dfs

就是dfs的标准格式,需要提前备份一下初始状态方便还原,还有就是如果已经找到了(即 $can=1$)或者步数超了就可以直接退出。主体就是二重循环枚举交换哪个方块。

void dfs(int step)
{
    if (can) return;
    if (check()) //已经全部消除完,输出方案
    {
        can=1;
        for (int i=1;i<step;i++) printf("%d %d %d\n",cur[i][0]-1,cur[i][1]-1,cur[i][2]);
        return;
    }
    if (step==n+1) return;
    MAP now;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=7;j++)
            now.s[i][j]=stat.s[i][j]; //备份
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!now.s[i][j]) continue;
            if (i==5) //在最右边一列只可能往左移
            {
                if (now.s[i-1][j]) continue;
                mv(i,j,-1); //移动
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1; //记录当前移动方式
                while (update()); //消除
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j]; //还原
                continue;
            }

            // 右移
            if (stat.s[i][j]!=stat.s[i+1][j])
            {
                mv(i,j,1);
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=1;
                while (update());
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j];
            }
            
            if (i>=2 && !now.s[i-1][j]) //左边为空往左移
            {
                mv(i,j,-1);
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
                while (update());
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j];
            }
        }
    }
}

代码

struct MAP{
    int s[10][10];
} stat;
int n,m,a,b,c,cur[10][3]; //0->x;1->y;2->left/right
bool can=0;
bool mark[10][10];

inline void drop()
{
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!mark[i][j]) continue;
            mark[i][j]=0;
            stat.s[i][j]=0;
        }
        for (int j=1;j<=7;j++)
        {
            if (stat.s[i][j]) continue; //找到空格删除
            int cnt=0;
            for (int k=j+1;k<=7;k++)
            {
                if (!stat.s[i][k]) continue;
                stat.s[i][j+cnt]=stat.s[i][k];
                cnt++;
                stat.s[i][k]=0;
                break;
            }
        }
    }
}

inline void mv(int x,int y,int s) //保证没有越界
{
    swap(stat.s[x][y],stat.s[x+s][y]);
    drop();
}

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

bool dfs_update(int x,int y,int fx,int fy,int step) //标记所有可以消除的
{
    bool can;
    if (step>=3) can=1;
    else can=0;
    if (stat.s[x+fx][y+fy]==stat.s[x][y]) can=can || dfs_update(x+fx,y+fy,fx,fy,step+1);
    if (can) mark[x][y]=1;
    return can;
}

inline bool update() //消去所有可以消的方块
{
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!stat.s[i][j]) continue;
            dfs_update(i,j,0,1,1); //纵向上
            dfs_update(i,j,0,-1,1); //纵向下
            dfs_update(i,j,1,0,1); //横向右
            dfs_update(i,j,-1,0,1); //横向左
        }
    } //mark checked
    int marked=0;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=7;j++)
            marked+=mark[i][j];
    drop();
    return marked;
}

void dfs(int step)
{
    if (can) return;
    if (check()) //已经全部消除完,校验每列第一个即可
    {
        can=1;
        for (int i=1;i<step;i++) printf("%d %d %d\n",cur[i][0]-1,cur[i][1]-1,cur[i][2]);
        return;
    }
    if (step==n+1) return;
    MAP now;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=7;j++)
            now.s[i][j]=stat.s[i][j]; //备份
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=7;j++)
        {
            if (!now.s[i][j]) continue;
            if (i==5) //只可能往左移
            {
                if (now.s[i-1][j]) continue;
                mv(i,j,-1);
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
                while (update());
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j];
                continue;
            }

            // 右移
            if (stat.s[i][j]!=stat.s[i+1][j])
            {
                mv(i,j,1);
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=1;
                while (update());
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j];
            }
            
            if (i>=2 && !now.s[i-1][j]) //左边为空往左移
            {
                mv(i,j,-1);
                cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
                while (update());
                dfs(step+1);
                for (int i=1;i<=5;i++)
                    for (int j=1;j<=7;j++)
                        stat.s[i][j]=now.s[i][j];
            }
        }
    }
}

int main()
{
    n=read();
    for (int i=1;i<=5;i++)
    {
        int m=0;
        a=read();
        while (a) 
        {
            stat.s[i][++m]=a;
            a=read();
        }
    } //read checked
    dfs(1);
    if (!can) printf("-1");
    return 0;
}

添加新评论