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; } |