Codeforces Round 941 (Div. 1) E. Connected Cubes（构造）

题目

思路来源

官方题解

题解

可以看下官方题解的7张图，还是比较清晰的，这里直接粘贴一下

来源：Codeforces Round #941 (Div. 1, Div. 2) Editorial - Codeforces

（1）原来的图

（2）对于偶数行，z轴正向伸长，长度为n+k

（3）对于奇数行，先通过L形状，使方向从z轴正向转换为x轴正向

（4）奇数行，x轴正向伸长为n+k

（4）奇数行，x轴正向伸长为n+k

（5）对于奇数行，z轴正向多出来的这k层，每一层填充k种颜色中的一种，

这样可以使得原来偶数行的原图里的颜色，和本次新增的奇数行的部分连通，

但是，新增部分的奇数行内部还没有连通

（6）对于偶数行，x轴正向多出来的这k层，每一层填充k种颜色中的一种，

这样可以使得原来奇数行的原图里的颜色，和本次新增的偶数行的部分连通，

但是，新增部分的偶数行内部还没有连通

（7）沿z轴正向，k种颜色每种颜色分配一个平行y轴的长条，

使得（5）中「新增部分的奇数行」彼此之间连通

（8）沿x轴正向，k种颜色每种颜色分配一个平行y轴的长条，

使得（6）中「新增部分的偶数行」彼此之间连通

（9）新增L型条，使每种颜色（7）（8）两部分连通，至此所有颜色已完全连通

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) cout<<(a);
#define pte(a) cout<<(a)<<endl;
#define ptlle(a) cout<<(a)<<endl;   
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=55;
typedef array<int,4> A;
int n,m,k,a[N][N];
vector<A>ans;
int main(){
    sci(n),sci(m),sci(k);
    rep(i,1,n){
        rep(j,1,m){
            sci(a[i][j]);
        }
    }
    rep(i,1,n){
        rep(j,1,m){
            if(j%2==0){
                rep(x,2,n+k){
                    ans.pb({i,j,x,a[i][j]});//1.偶行竖条
                }   
            }
            else{
                //(1,j,1)-(1,j,2) xOz平面
                rep(x,2,n+1-i){
                    ans.pb({i,j,x,a[i][j]});//2.奇行竖条
                }
                rep(x,i+1,n+k){
                    ans.pb({x,j,n+1-i,a[i][j]});//3.奇行横条
                }
            }
        }
    }
    rep(c,1,k){
        rep(j,1,m){
            if(j&1){
                rep(i,1,n){
                    ans.pb({i,j,n+c,c});//4.xOy平面奇行平铺一层
                }
            }
            else{
                rep(i,1,n){
                    ans.pb({n+c,j,i,c});//5.yOz平面偶行平铺一层
                } 
            }
        }
    }
    rep(c,1,k){
        rep(j,1,m){
            ans.pb({n+1,j,n+c,c});//6.每个颜色y轴铺一条 沿z轴正向堆叠
        }
    }
    rep(c,2,k){
        rep(j,1,m){
            ans.pb({n+c,j,n+1,c});//7.每个颜色y轴铺一条 沿x轴正向堆叠
        }
        //8.使6、7两种竖条联通
        rep(i,2,c){
            ans.pb({n+i,1,n+c,c});
        }
        rep(i,2,c-1){
            ans.pb({n+c,1,n+i,c});
        }
    }
    pte(SZ(ans));
    for(auto &x:ans){
        printf("%d %d %d %d\n",x[0],x[1],x[2],x[3]);
    }
    return 0;
}