算法

(搜索，剪枝) $O((nm)^5)$

由于最多枚举 $5$ 步，数据范围很小，因此直接暴搜即可。

搜索顺序：依次枚举每一步选择哪个方块，向左右哪个方向移动。

剪枝情况有三种：

1. 向右移动时，如果右侧的方块颜色和当前方块颜色相同，则剪枝。这是由于交换之后状态没有任何变化。，由于题目中要求步数恰好是 $n$ 的方案，因此这个无意义的操作可能被用来填补操作步数，因此不能被剪掉。
2. 向左移动时，如果左侧有方块，则直接减掉。这是由于输出的答案要求字典序最小，如果左侧有方块，那么将左侧的方块向右移动的字典序小于将当前方块向左移动的字典序。
3. 当某种颜色的方块数量大于0小于等于2时，一定无解，直接剪枝。

时间复杂度

假设有 $n$ 行 $m$ 列，则总共有 $nm$ 个格子，一共移动 $5$ 步，最坏情况下每一步都有 $(nm)^5$ 种选法，因此最坏情况下的时间复杂度是 $O((nm)^5)$。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int g[5][7], bg[5][5][7];
int cnt[11], bcnt[5][11];
bool st[5][7];

struct Path
{
    int x, y, d;
}path[5];

void move(int a, int b, int c)
{
    swap(g[a][b], g[c][b]);

    while (true)
    {
        bool flag = true;
        // 处理悬空方格
        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;
        }

        memset(st, 0, sizeof st);
        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 = false;
                    }
                    else
                    {
                        l = 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 = false;
                        }
                    }
                }

        if (flag) break;
        for (int x = 0; x < 5; x ++ )
            for (int y = 0; y < 7; y ++ )
                if (st[x][y])
                {
                    cnt[0] -- ;
                    cnt[g[x][y]] -- ;
                    g[x][y] = 0;
                }
    }
}

bool dfs(int u)
{
    if (u == n) return !cnt[0];

    for (int i = 1; i <= 10; i ++ )
        if (cnt[i] == 1 || cnt[i] == 2)
            return false;

    // 枚举所有操作
    memcpy(bg[u], g, sizeof g);
    memcpy(bcnt[u], cnt, sizeof cnt);
    for (int x = 0; x < 5; x ++ )
        for (int y = 0; y < 7; y ++ )
            if (g[x][y])
            {
                int nx = x + 1;
                if (nx < 5)
                {
                    path[u] = {x, y, 1};
                    move(x, y, nx);
                    if (dfs(u + 1)) return true;
                    memcpy(g, bg[u], sizeof g);
                    memcpy(cnt, bcnt[u], sizeof cnt);
                }

                nx = x - 1;
                if (nx >= 0 && !g[nx][y])
                {
                    path[u] = {x, y, -1};
                    move(x, y, nx);
                    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 x = 0; x < 5; x ++ )
    {
        int t, y = 0;
        while (scanf("%d", &t), t)
        {
            cnt[0] ++ ;
            cnt[t] ++ ;
            g[x][y ++ ] = t;
        }
    }

    if (dfs(0))
    {
        for (int i = 0; i < n; i ++ ) printf("%d %d %d\n", path[i].x, path[i].y, path[i].d);
    }
    else puts("-1");

    return 0;
}