Luogu P1225 黑白棋游戏 题解

(Updated: )
oi

Preface

题目链接

这题真的恶心，状压写错了调半天。。。

Description

给定一个 $4\times 4$ 的棋盘，每一格放一个棋子，共有 $8$ 个黑棋，$8$ 个白棋。每次可以交换相邻两个格子的棋子，问最少要多少步才能从初始状态到达最终状态。并且需要输出交换方法。

Solution

由于棋盘十分小（只有 $4\times 4$ ），所以考虑食用 $bfs$。

这道题主要问题是状态如何考虑。

由于只有黑棋和白棋，所以很自然的就想到了状压的思想。

我们可以考虑将整个棋盘直接状压成一个 $16$ 位二进制数，再进行 $bfs$ 转移。

$2^0$ $2^1$ $2^2$ $2^3$
$2^4$ $2^5$ $2^6$ $2^7$
$2^8$ $2^9$ $2^{10}$ $2^{11}$
$2^{12}$ $2^{13}$ $2^{14}$ $2^{15}$

1
2
3
4
5
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;//直接状压
    }

那么在 $bfs$ 的时候，只需要根据这个状压方法提取出需要交换的两位，并且暴力交换后再压回去即可。

1
2
3
4
5
6
7
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;
}

另外，在 $bfs$ 的过程中，记录一下父亲及路径即可，最后递归输出。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 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;
}