题解：CF1025E Colored Cubes

· · 题解

考虑用爬山法。
随机一个排列，按顺序去推立方体。对于每个立方体，随机一个数，决定先横着推还是竖着推，然后按最短路径推立方体，如果前面的格子上有其它立方体了，就把它们按与目标方向垂直的方向推。由于 m\le n 所以一行（一列）不可能构成一条线挡路，所以可以随便推。

代码

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=60,maxm=60;
int x[maxm],y[maxm],xx[maxm],yy[maxm],n,m,h[maxn][maxn],yux[maxm],yuy[maxm],cnt;
tuple<int,int,int,int>ans[101000];
void move(int x,int y,int xx,int yy){
    ans[++cnt]=make_tuple(x,y,xx,yy);
    int id=h[x][y];
    h[x][y]=0,h[xx][yy]=id;
    ::x[id]=xx,::y[id]=yy;
}
bool t1(int x,int y,int fx){
    if(x<1||x>n||y<1||y>n) return 0;
    if(h[x][y]==0) return 1;
    if(t1(x,y+fx,fx)){move(x,y,x,y+fx);return 1;}
    return 0;
}
void t12(int x,int y){
    if(t1(x,y,1)) return ;
    t1(x,y,-1);
}
bool t2(int x,int y,int fx){
    if(x<1||x>n||y<1||y>n) return 0;
    if(h[x][y]==0) return 1;
    if(t2(x+fx,y,fx)){move(x,y,x+fx,y);return 1;}
    return 0;
}
void t22(int x,int y){
    if(t2(x,y,-1)) return ;
    t2(x,y,1);
}
void work1(int i){
    int x=::x[i],y=::y[i];
    int mbx=xx[i],mby=yy[i];
    while(x<mbx){
        int xx=x+1,yy=y;
        t12(xx,yy);
        move(x,y,xx,yy);
        x=xx,y=yy;
    }
    while(x>mbx){
        int xx=x-1,yy=y;
        t12(xx,yy);
        move(x,y,xx,yy);
        x=xx,y=yy;
    }
}
void work2(int i){
    int x=::x[i],y=::y[i];
    int mbx=xx[i],mby=yy[i];
    while(y<mby){
        int xx=x,yy=y+1;
        t22(xx,yy);
        move(x,y,xx,yy);
        x=xx,y=yy;
    }
    while(y>mby){
        int xx=x,yy=y-1;
        t22(xx,yy);
        move(x,y,xx,yy);
        x=xx,y=yy;
    }
}
int p[maxm];
bool check(){for(int i=1;i<=m;i++) if(x[i]!=xx[i]||y[i]!=yy[i]) return 0;return 1;}
signed main(){
    mt19937 Rand(20120515);
    read(n,m);
    for(int i=1;i<=m;i++) read(x[i],y[i]),h[x[i]][y[i]]=i,yux[i]=x[i],yuy[i]=y[i],p[i]=i;
    for(int i=1;i<=m;i++) read(xx[i],yy[i]);
    while(!check()){
        shuffle(p+1,p+1+m,Rand);
        for(int i=1;i<=m;i++){
            int id=p[i];
            if(Rand()&1) work1(id),work2(id);
            else work2(id),work1(id);
        }
    }
    write(cnt),write("\n");
    for(int i=1;i<=cnt;i++) write(get<0>(ans[i]),get<1>(ans[i]),get<2>(ans[i]),get<3>(ans[i]));
    return 0;
}