算法思路

y总：爆搜最重要的就是搜索顺序

• 很明显这道题的搜索顺序可以找到：依次枚举每一位数字，判断它向左或者向右移动是否合法。但是如果真的这样做也是不可取的。因为格子有35个所以，每个各种有两种变化状态，最多扩展5次并且每次都要改变当前的状态为35所以总的时间复杂度为(35 * 2) ^ 5 * 35 肯定超时，因此就要想剪枝。
• 剪枝一：当前状态中某一个值的数目为1个或者两个那么肯定无解，直接回溯。
• 剪枝二：因为一个数向左移动如果它的左边存在数的话等价于它右边的数向右移动，由于题目中要求答案的字典序最小，因此这种情况直接略过，除非它的左边没有数才做。
• 剪枝三：当一个数的右边和它本身的数值一样的话那么我们就不做它，但是题目中要求恰好为n次，因此可能存在移动无用方案的解，因此不可取。
  加上上面的剪枝就可以1秒ac了 nice 爆搜加剪枝的时间复杂度为玄学问题：至于过不过就需要看脸了

C++ 代码

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

using namespace std;
int g[5][7], bg[5][5][7];
int cnt[5 * 7], bcnt[5][5 * 7];
struct Seq
{
    int x, y, dir;
}path[5];
bool st[5][7];
int n;

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

    while(true)
    {
        bool flag = false;
        for(int i = 0; i < 5; i ++){ 
            int z = 0;
            for(int j = 0; j < 7; j ++)
                if(g[i][j])
                    g[i][z ++] = g[i][j];
            while(z < 7)g[i][z ++] = 0;
        }
        memset(st, 0, sizeof st);
        for(int i = 0; i < 5; i ++)
            for(int j = 0; j < 7; j ++)
                if(g[i][j])
                {
                    int l = i, r = i;
                    while(l - 1 >= 0 && g[l - 1][j] == g[i][j])l --;
                    while(r + 1 < 5 && g[r + 1][j] == g[i][j])r ++;

                    if(r - l + 1 >= 3)
                    {
                        st[i][j] = true;
                        flag = true;
                    }

                    {
                        int l = j, r = j;
                        while(l - 1 >= 0 && g[i][l - 1] == g[i][j])l --;
                        while(r + 1 < 7 && g[i][r + 1] == g[i][j])r ++;
                        if(r - l + 1 >= 3)
                        {
                            st[i][j] = true;
                            flag = true;
                        }
                    }
                }
        if(flag)
        {
            for(int i = 0; i < 5; i ++) 
                for(int j = 0; j < 7; j ++)
                    if(st[i][j])
                    {
                        cnt[0] --;
                        cnt[g[i][j]] --;
                        g[i][j] = 0;
                    }
        }
        else break;

    }
}

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

    for(int i = 0; i < 5; i ++)
        for(int j = 0; j < 7; j ++)
            if(cnt[g[i][j]] == 1 || cnt[g[i][j]] == 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])continue;
            int rx = i + 1;
            if(rx < 5)
            {
                path[u] = {i, j, 1};
                move(i, j, rx);
                if(dfs(u + 1)) return true;
                memcpy(g, bg[u], sizeof g);
                memcpy(cnt, bcnt[u], sizeof cnt);
            }
            int lx = i - 1;
            if(lx >= 0 && !g[lx][j])
            {
                path[u] = {i, j, -1};
                move(i, j, lx);
                if(dfs(u + 1))return true;

                memcpy(g, bg[u], sizeof g);
                memcpy(cnt, bcnt[u], sizeof cnt);
            }            
        }
    return false;
}
int main()
{
    cin >> n;
    for(int i = 0; i < 5; i ++)
    {
        int t, j = 0;
        while(cin >> t, t)
        {
            g[i][j ++] = t;
            cnt[t] ++;
            cnt[0] ++;
        }
    }

    if(dfs(0))
    {
        for(int i = 0; i < n; i ++)cout << path[i].x << ' ' << path[i].y << ' '<< path[i].dir << endl;
    }
    else puts("-1");

    return 0;
}