Luogu P1225 黑白棋游戏 题解

for(int i=0;i<4;i++)
    for(int j=0;j<4;j++){
        char c=gc();W(c!='0'&&c!='1') c=gc();
        S=(c&15)<<i*4+j;//直接状压
    }

I int v(int p,int x,int y){return p>>x*4+y&1;}//获取该状态下的该位置权值
I int swp(int p,int x,int y,int xx,int yy){
    int v1=v(p,x,y),v2=v(p,xx,yy);//获取这两位的权值
    p&=((1<<16)-1)^1<<x*4+y,p&=((1<<16)-1)^1<<xx*4+yy,//把该状态下的这两位清空
    p=v2<<x*4+y,p=v1<<xx*4+yy;//赋值
    return p;
}

// Problem: P1225 黑白棋游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1225
// Memory Limit: 125 MB
// Time Limit: 1000 ms

// Auther: yzxoi
// Site: yzxoi.top 

#include<cstdio>
#include<queue>
#include<cstring>
#define W while
#define I inline
#define LL long long
#define gc getchar
#define ig(c) ('0'<=(c)&&(c)<='9')
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
I int read(){int x=0,f=1;char c=gc();W(!ig(c)) f=c=='-'?-1:f,c=gc();W(ig(c)) x=(x<<3)+(x<<1)+(c&15),c=gc();return x*f;}
I void write(int x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
const int N=114514;
const int dx[]={0,0,1,-1},
          dy[]={1,-1,0,0};
int S,T,dis[N],vis[N],pre[N];
struct node{int x,y,xx,yy;}pp[N];
std::queue<int> q;
I int v(int p,int x,int y){return p>>x*4+y&1;}
I int swp(int p,int x,int y,int xx,int yy){int v1=v(p,x,y),v2=v(p,xx,yy);p&=((1<<16)-1)^1<<x*4+y,p&=((1<<16)-1)^1<<xx*4+yy,p=v2<<x*4+y,p=v1<<xx*4+yy;return p;}
I void print(int p){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            printf("%d ",p>>i*4+j&1);
        }
        pc('\n');
    }
}
I void bfs(int x){
    W(!q.empty()) q.pop();
    q.push(x);
    memset(dis,63,sizeof(dis));
    dis[x]=0;
    W(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                for(int k=0;k<4;k++){
                    int xx=i+dx[k],yy=j+dy[k],p;
                    if(xx>=0&&xx<4&&yy>=0&&yy<4&&v(u,i,j)^v(u,xx,yy)) dis[p=swp(u,i,j,xx,yy)]>dis[u]+1&&(dis[p]=dis[u]+1,pre[p]=u,pp[p]=(node){i,j,xx,yy},!vis[p]&&(vis[p]=1,q.push(p),0),0);
                }
    }
}
I void printpre(int x){
    if(pre[x]) printpre(pre[x]);
    else return ;
    write(pp[x].x+1),write(pp[x].y+1),write(pp[x].xx+1),write(pp[x].yy+1),pc('\n');
}
int main(){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++){
            char c=gc();W(c!='0'&&c!='1') c=gc();
            S=(c&15)<<i*4+j;
        }
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++){
            char c=gc();W(c!='0'&&c!='1') c=gc();
            T=(c&15)<<i*4+j;
        }
    bfs(S);
    write(dis[T]),pc('\n');
    printpre(T);
    return 0;
}