题解 | Mayan游戏-NOIP2011提高组复赛

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int g[5][7];
int cnt[11];
int bg[5][5][7];
int bcnt[5][11];
bool st[5][7];
 
struct Move
{
    int x, y, d;
}
path[5];
 
void move(int j, int i, int k)
{
    swap(g[i][j], g[k][j]);
 
    while (true)
    {
        bool flag = false;
        memset(st, false, sizeof st);
 
        for (int x = 0; x < 5; x++)
        {
            int z = 0;
            for (int y = 0; y < 7; y++)
                if (g[x][y])
                    g[x][z++] = g[x][y];
            while (z < 7) g[x][z++] = 0;
        }
 
        for (int x = 0; x < 5; x++)
            for (int y = 0; y < 7; y++)
                if (g[x][y])
                {
                    int l = x, r = x;
                    while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
                    while (r + 1 < 5 && g[r + 1][y] == g[x][y]) r++;
                    if (r - l + 1 >= 3)
                    {
                        st[x][y] = true;
                        flag = true;
                    }
                    else
                    {
                        l = y, r = y;
                        while (l - 1 >= 0 && g[x][l - 1] == g[x][y]) l--;
                        while (r + 1 < 7 && g[x][r + 1] == g[x][y]) r++;
                        if (r - l + 1 >= 3)
                        {
                            st[x][y] = true;
                            flag = true;
                        }
                    }
                }
 
        if (flag)
        {
            for (int x = 0; x < 5; x++)
                for (int y = 0; y < 7; y++)
                    if (st[x][y])
                    {
                        cnt[g[x][y]]--;
                        g[x][y] = 0;
                    }
        }
        else break;
    }
}
 
bool dfs(int u)
{
    if (u == n)
    {
        for (int i = 1; i <= 10; i++)
            if (cnt[i])
                return false;
        return true;
    }
 
    for (int i = 1; i <= 10; i++)
        if (cnt[i] && cnt[i] <= 2)
            return false;
 
    memcpy(bg[u], g, sizeof g);
    memcpy(bcnt[u], cnt, sizeof cnt);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 7; j++)
            if (g[i][j])
            {
                int k = i + 1;
                if (k < 5 && g[i][j] != g[k][j])
                {
                    path[u] = {
                        i, j, 1
                    };
                    move(j, i, k);
 
                    if (dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }
 
                k = i - 1;
                if (k >= 0 && !g[k][j])
                {
                    path[u] = {
                        i, j, -1
                    };
                    move(j, i, k);
                    if (dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }
            }
 
    return false;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 5; i++)
    {
        int j = 0, y;
        while (scanf("%d", &y), y)
        {
            cnt[y]++;
            g[i][j++] = y;
        }
    }
 
    if (!dfs(0)) puts("-1");
    else
    {
        for (int i = 0; i < n; i++) printf("%d %d %d\n", path[i].x, path[i].y, path[i].d);
    }
 
    return 0;
}