P1225 黑白棋游戏
简化版P4289 [HAOI2008]移动玩具。
题意简述
给你一个 4\times4 的 01 矩阵，每次可以交换相邻的一对 0 和 1 。求最小操作次数使得初始矩阵变成目标矩阵，并输出如何操作。
Solution
有始有终考虑**双向广搜**。
---
双向广搜是啥？
从起点和终点分别拓展状态，当两边的解答树第一次重合时找到答案。
需要特判一开始就是答案。
注意还原状态。
递归输出方案即可。
[还是不太明白点这里](https://www.luogu.com.cn/blog/nizhuan/xue-xi-bi-ji-shuang-xiang-guang-sou-hu-01bfs)
具体来说每一个数字对应一个矩阵，每次从队头取出数字还原矩阵。对于每一个 $1$ 拓展矩阵。重新状压判重，记录前驱方便后面递归输出。
## Code
```cpp
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
int s,e,vis[70000],a[10][10],step[70000],nxt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
pair <int,int> last[70000];
queue <int> q;
void prints(int x)//递归输出
{
if(!x) return ;
prints(last[x].first);
if(last[x].second) printf("%d\n",last[x].second); return ;
}
void printe(int x)
{
if(!x) return ;
if(last[x].second) printf("%d\n",last[x].second);
printe(last[x].first); return ;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
char t;//状压
for(int i=1;i<=16;i++) {scanf(" %c",&t); s=(s<<1)+t-'0';}
for(int i=1;i<=16;i++) {scanf(" %c",&t); e=(e<<1)+t-'0';}
if(s == e) return printf("0"),0;
vis[s]=1; vis[e]=2; step[s]=0; step[e]=0; last[s].first=last[e].first=0;
q.push(s); q.push(e);
int x,now;
while(!q.empty())
{
x=now=q.front(); q.pop();
for(int i=4;i;i--)
for(int j=4;j;j--) {a[i][j]=x&1; x>>=1;}
for(int i=1,nx,ny;i<=4;i++)
for(int j=1;j<=4;j++)
if(a[i][j])
for(int u=0;u<4;u++)
{
nx=i+nxt[u][0]; ny=j+nxt[u][1]; x=0;
if(nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
if(!a[nx][ny])
{
a[i][j]=0; a[nx][ny]=1;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++) x=(x<<1)+a[k][l];
a[i][j]=1; a[nx][ny]=0;
if(vis[x]+vis[now] == 3)//找到答案
{
if(vis[x] == 1) x^=now^=x^=now;
printf("%d\n",step[x]+step[now]+1);
prints(now); printf("%d\n",i*1000+j*100+nx*10+ny); printe(x);
return 0;
}
if(vis[x]) continue;
last[x].first=now; last[x].second=i*1000+j*100+nx*10+ny;
vis[x]=vis[now]; step[x]=step[now]+1; q.push(x);
}
}
}
// fclose(stdin); fclose(stdout);
return 0;
}
```
双向广搜！很快啊！不加优化截至2021年5月1日跑到了最优解第一页。
# $\text{Thank you for your reading!}