Noip2011 Mayan游戏 搜索 + 模拟 + 剪枝

写了一下午，终于AC了。

由于n<=5, 所以不需要太多的剪枝和技巧也能过。可以将操作后的消方块和下落和剪枝函数写到一个结构体中，这样会减少调试难度，更加简洁。

可以采用如下剪枝：

1. 如果当前有一种颜色少于两个，则一定无解。

2. 如果相邻颜色相同则不交换。

3. 优先考虑右移

4. 其实可以开一个unordered_map来避免重复搜索，由于笔者已经筋疲力尽，就没有进行这部优化（但其实n的规模太小，不开也无所谓）。

代码：

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<deque>

using namespace std;;

const int n = 7;

const int m = 5;

int board[10][10], spare[10][10], target;

struct Ans

{

    int x,y,g;

    Ans(int x = 0, int y = 0,int g = 0):x(x),y(y),g(g){}

};

deque<Ans>Q;

struct Operation

{

    inline int get_num()

    {

        int cnt = 0;

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

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

                if(spare[i][j])++cnt;

        return cnt;

    }

    inline int cut()

    {

        int col[16];

        memset(col,0,sizeof(col));

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

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

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

            if(col[i] && col[i] <= 2)return 1;

        return 0;

    }

    inline int clear_block()

    {

        int flag = 0;

        int mark[10][10];

        memset(mark,0,sizeof(mark));

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

        {

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

            {

                if(!spare[i][j])continue;

                if(i + 2 <= n)

                {

                    int cur = i;

                    while(spare[cur + 1][j] == spare[cur][j]) ++cur;

                    if(cur - i + 1 >= 3)

                    {

                        flag = 1;

                        int y = i;

                        while(spare[y][j] == spare[i][j]) mark[y][j] = 1, y += 1;

                    }

                }

                if(j + 2 <= m)

                {

                    int cur = j;

                    while(spare[i][cur + 1] == spare[i][cur])++cur;

                    if(cur - j + 1 >= 3)

                    {

                        flag = 1;

                        int y = j;

                        while(spare[i][y] == spare[i][j]) mark[i][y] = 1, y += 1;

                    }

                }

            }

        }

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

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

                if(mark[i][j])spare[i][j] = 0;

        return flag;

    }

    inline void down()

    {

        for(int col = 1; col <= m; ++col)

        {

            int bottom = n, cur = n;

            while(bottom >= 1 && cur >= 1)

            {

                while(spare[bottom][col] && bottom >= 1) --bottom;

                cur = bottom;

                while(cur >= 1 && !spare[cur][col]) --cur;

                if(cur >= 1)

                {

                    int i = bottom ,j = cur;

                    while(spare[j][col] && j >= 1 && i >= 1)

                    {

                        spare[i][col] = spare[j][col];

                        spare[j][col] = 0;

                        --i;

                        --j;

                    }

                }

            }

        }

    }

    inline void update()

    {

        down();

        while(clear_block()) down();

    }

}T;

void dfs(int nums,int arr[10][10])

{

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

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

    T.update();

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

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

    if(nums == target)

    {

        if(!T.get_num())

        {

            while(!Q.empty())

            {

                Ans p = Q.front();

                printf("%d %d %d\n",p.x-1, 7-p.y, p.g);

                Q.pop_front();

            }

            exit(0);

        }

        return;

    }

    if(!T.get_num() || T.cut())return;

    int h[10][10];

    memset(h,0,sizeof(h));

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

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

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

        for(int i = 7; i >= 1;--i)

        {

            if(!h[i][j])continue;

            if(j < m && arr[i][j] != arr[i][j+1])

            {

                swap(h[i][j],h[i][j+1]);

                Q.push_back(Ans(j,i,1));

                dfs(nums+1,h);

                Q.pop_back();

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

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

            }

            if(j > 1 && !arr[i][j-1])

            {

                swap(h[i][j],h[i][j-1]);

                Q.push_back(Ans(j,i,-1));

                dfs(nums+1,h);

                Q.pop_back();

                swap(h[i][j],h[i][j-1]);

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

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

            }

        }

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d",&target);

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

    {

        for(int j = 7; ;--j)

        {

            int a;

            scanf("%d",&a);

            if(!a)break;

            board[j][i] = a;

        }

    }

    dfs(0,board);

    printf("-1");

    return 0;

}