mayan 游戏真是毒瘤

如题

真坑呀！！！

可算过了

我率先达到了氧气富有化

先是改变时没有fall。40分

然后是fall函数写慢了 tle 50分

---

.

---

上代码

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

struct node

{

    int m[6][9];

    bool era[6][9];

    int t[15];

    bool can()

    {

        bool ca=false;

        for(int i=1;i<=5;i++)

            for(int j=1;m[i][j];j++)

            {

                if(j-1&&m[i][j-1]==m[i][j]&&m[i][j]==m[i][j+1]&&m[i][j-1]==m[i][j+1])//暴力判断是否可以消除

                {

                    era[i][j-1]=era[i][j]=era[i][j+1]=true;//ps 如果是多于四个方格，我们可以拆成3个方格重叠。这也就是为什么要era消除标记，而不是直接消除

                    ca=true;

                }

                if(i-1&&m[i-1][j]==m[i][j]&&m[i][j]==m[i+1][j]&&m[i-1][j]==m[i+1][j])

                {

                    era[i-1][j]=era[i][j]=era[i+1][j]=true;//所以，这样的话，十字行就可以处理了

                    ca=true;

                }

            }

        return ca;

    }

    void fall()

    {

    	int pass[50],top;

		for(int i=1;i<=5;i++)

		{

			top=0;

			for(int j=1;j<=7;j++)

				if(m[i][j])//先从下到上扫一遍，将有颜色的 方格储存下来。

				{

					pass[++top]=m[i][j];

					m[i][j]=0;

				}

			for(int j=1;j<=top;j++)

				m[i][j]=pass[j];//再安回去

		}

    }

    void clear()

    {

        for(int i=1;i<=5;i++)

            for(int j=1;j<=7;j++)

                if(era[i][j])//照着标记消就可以了

                {

                    m[i][j]=0;

                    t[m[i][j]]-=1;

                    era[i][j]=false;//顺便重置一下

                }

        fall();//掉落

    }

    bool judge1()

    {

        int sum=0;

        for(int i=1;i<=5;i++)

            for(int j=1;j<=5;j++)

                sum+=m[i][j];

        return sum;//全0时结束

    }

    bool judge2()

    {

        for(int i=1;i<=10;i++)

            t[i]=0;

        for(int i=1;i<=5;i++)

            for(int j=1;j<=7;j++)

                t[m[i][j]]+=1;

        for(int i=1;i<=10;i++)

            if(t[i]>=1&&t[i]<=2)

                return true;

        return false;//如果一种颜色的方格的个数大于1而且小于2，那么这种颜色的方块一定就消不了了，直接退出

    }

};

node a;

int n;

bool found;

int stack[5555][3];

void dfs(int step)

{

    if(a.judge2())

        return ;

    if(found)

        return ;

    if(step==n)

    {

        if(a.judge1())

            return ;

        found=true;

        return ;

    }

    node b=a;

    for(int i=1;i<=5;i++)

        for(int j=1;j<=7;j++)

        {

            if(a.m[i][j]!=a.m[i+1][j]&&i+1!=6&&a.m[i][j])

            {

                swap(a.m[i][j],a.m[i+1][j]);

                a.fall();

                while(a.can())

                    a.clear();

                dfs(step+1);

                a=b;

                stack[step][0]=i;

                stack[step][1]=j;

                stack[step][2]=1;

            }

            if(found)

                return;

            if(!a.m[i-1][j]&&a.m[i][j]&&i-1!=0)

            {

                swap(a.m[i][j],a.m[i-1][j]);

                a.fall();

                while(a.can())

                    a.clear();

                dfs(step+1);

                a=b;

                stack[step][0]=i;

                stack[step][1]=j;

                stack[step][2]=-1;

            if(found)

                return ;

            }

        }

}

int main()

{

    scanf("%d",&n);

    int j=1;

    for(int i=1;i<=5;i++)

    {

        j=1;

        scanf("%d",&a.m[i][j]);

        a.t[a.m[i][j]]+=1;

        while(a.m[i][j])

        {

            j+=1;

            scanf("%d",&a.m[i][j]);

            a.t[a.m[i][j]]+=1;

        }

    }

    while(a.can())

        a.clear();

    dfs(0);

    if(found)

    {

        for(int i=0;i<n;i++)

            printf("%d %d %d\n",stack[i][0]-1,stack[i][1]-1,stack[i][2]);

        return 0;

    }

    printf("-1");

    return 0;

}

对于这道题

难点我觉得不是思维的难度

而是码力。真的时纯靠码力

以及算法的优化

fall函数我一开始就写了个n^2算法

华丽丽的tle