CF1965E 解题报告

· · 题解

问候

致歉：由于本人在学校训练无法使用 MC，故只能把三维图像画成几幅二维图。请读者在脑海里把它们斗起来。

清新又巧妙，绝世好构造。

析

等于是给每一个颜色指定一个约会地点然后让所有同色色块全部沿自己的路径润过去，并保证不同种色块的赴约路径簇不交就可以了。

但是我们发现把所有色块的赴约路径放到空间上考虑实在是无从下手，所以我们应该思考的是如何减小赴约路径簇不交的限制给我们的影响。

经过一番随机思考，我发现可以让每一列块块彼此分开，然后把它们垒高（向上粘贴），就能把每一次的赴约路径压成一个平面，呈鱼骨型。

问题来到了如何把块块分开。其实这个并不难，简单结论是：将第 k 靠左的列，先往上涨 (m - k) 格，再向右粘 (k - 1) 格，最后往上涨 (k - 1) 格，即得。

但是如果每次都垒高所有块块，并且鱼骨的横向刺每次都插到底，就过不了。所以已经连通过的颜色就不必再垒高，横向刺插到最后一个需要遍历的地方就不再往后插了。

给一个图解。箭头的指向表示从下往上数的层序先后。

码

::::info[Code.]

#include<bits/stdc++.h>
#define lin long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 55
#define endl "\n"
#define nullptr 0
#define rep(i ,a ,b) for (int i = a ;i <= b ;i ++)
#define per(i ,a ,b) for (int i = b ;i >= a ;i --)
#define vt vector
#define pb push_back
#define pii pair <int ,int>
#define I ios :: sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);


using namespace std;


void chkmnm (int &x ,int y)
{
    x = min (x ,y);
    return ;
}


int n ,m ,k ,a[maxn][maxn] ,tong[maxn * maxn];


struct node
{
    int x ,y ,z ,col;

    void op ()
    {
        cout << x << " " << y << " " << z << " " << col << endl;
        return ;
    }

    void zhang () // 涨
    {
        z ++;
        return ;
    }

    void you () // 右
    {
        y ++;
        return ;
    }

} ;


vt <node> vec;


node sp[maxn][maxn];


int vis[maxn][maxn] ,mnm[maxn][maxn]; // mnm[i][j] 表示 y = i 时颜色 j 出现的最小 x


signed main()
{
    I AK CSP

    cin >> n >> m >> k;
    rep (i ,1 ,50)
        rep (j ,1 ,50)
            mnm[i][j] = 1e18;
    rep (i ,1 ,n)
        rep (j ,1 ,m)
            cin >> a[i][j] ,tong[a[i][j]] = 1 ,chkmnm (mnm[j][a[i][j]] ,i);

    rep (kth ,1 ,m) // 初始把块块分开
    {
        rep (i ,1 ,n)
        {
            node cur = {i ,kth ,1 ,a[i][kth]};
            rep (t ,1 ,m - kth)
                cur.zhang () ,vec.pb (cur);
            rep (t ,1 ,kth - 1)
                cur.you () ,vec.pb (cur);
            rep (t ,1 ,kth - 1)
                cur.zhang () ,vec.pb (cur);
            sp[i][kth] = cur;
        }
    }

    int curhgt = m;
    rep (t ,1 ,k)
    {
        curhgt ++;
        rep (i ,1 ,n) // 往上垒
            rep (j ,1 ,m)
            {
                if (! vis[i][j])
                    sp[i][j].zhang () ,vec.pb (sp[i][j]);
                if (sp[i][j].col == t)
                    vis[i][j] = 1;
            }
        rep (i ,1 ,(m << 1) - 1)
            vec.pb ({n + 1 ,i ,curhgt ,t}); // 鱼脊柱
        rep (i ,1 ,m - 1)
            rep (j ,(i == m - 1) ? min (mnm[i][t] ,mnm[i + 1][t]) : mnm[i][t] ,n) // 插到最后一个需要连通的位置
                vec.pb ({j ,(i << 1) ,curhgt ,t}); // 横向刺
    }

    if (vec.size () > 400000)
        cout << - 1 << endl;
    else
    {
        cout << vec.size () << endl;
        for (node zc : vec)
            zc.op ();
    }

    return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.

::::