广搜
4*4 的方阵只有 0 和 1
显然可以状态压缩
（如样例的开始状态压缩后就是1111000011100010）
为了加快速度用了双向广搜（顺便学了一下双向广搜）
双向广搜顾名思义
就是从起点和终点两个方向广搜
每次选择扩展步数少的扩展一层
然后一旦一个状态被两边都找到了
那就把两边的步数加一下，就是答案了
然后要注意位运算的细节
具体实现看代码吧
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
int p,stp;
};//广搜的队列，p表示状态,stp表示当前走了几步
queue <node> q[];
bool pd[][];//记忆化,pd[i][]为到i状态需要的最少步数
int ans,st,lst;
inline void add(int k,int p,int stp)
//尝试把状态p加入队列
{
if(pd[p][k^]||(p==st&&k)||(p==lst&&k==))//如果另一边已经找过了或者到了另一边的起点
//因为在起点和终点的pd为0 所以要特判一下
{
ans=stp+pd[p][k^];//更新ans
return;//直接返回
}
if(pd[p][k]||p==st||p==lst) return;//如果找过了或者回到开始点,直接返回 //否则
pd[p][k]=stp;//更新pd
node t; t.p=p; t.stp=stp;
q[k].push(t);//加入队列
}
inline void bfs()
{
int k= q[].size()<q[].size();//确定要从哪一边扩展
int now=q[k].front().stp;
while(!q[k].empty())
{
node t=q[k].front();
if(t.stp>now||ans) break;//保证一次只扩展一层
q[k].pop();//（细节）要先判断再弹出
for(int i=;i>=;i--)//向左移动
{
if(i%==) continue;//注意如果在边界就不能动
if( !(t.p& (<<i) ) || t.p& ( <<(i+) ) ) continue;//判断
add(k, t.p^ (<<i) ^ ( <<(i+) ), t.stp+);//直接异或一波得到下一步的状态
}
for(int i=;i>=;i--)//向右
{
if(i%==) continue;//同样判断
if( !(t.p& (<<i) ) || t.p& (<<(i-) ) ) continue;
add(k, t.p^ (<<i) ^ ( <<(i-) ), t.stp+);
}//同上
for(int i=;i>=;i--)//向上，注意i的范围
{
if( !(t.p& (<<i) ) || t.p& (<<(i+) ) ) continue;
add(k, t.p^ (<<i) ^ ( <<(i+) ), t.stp+);
}//同上
for(int i=;i>=;i--)//向上，同样注意i
{
if( !(t.p& (<<i) ) || t.p& (<<(i-) ) ) continue;
add(k, t.p^ (<<i) ^ ( <<(i-) ), t.stp+);
}//同上
}
}
int main()
{
char ss[]; memset(ss,,sizeof(ss));
for(int i=;i<;i++)
{
cin>>ss;
for(int j=;j<;j++)
st+=( (ss[j]-'')<<(-i*-j) );
}//读入状态
node t; t.p=st; t.stp=;
q[].push(t);//开始状态压入队列 for(int i=;i<;i++)
{
cin>>ss;
for(int j=;j<;j++)
lst+=( (ss[j]-'')<<(-i*-j) );
}
t.p=lst; q[].push(t);//同上 if(st==lst)//特判一波起点和终点状态相同的情况
{
cout<<;
return ;
} while(!ans)
bfs();//广搜找ans
cout<<ans;
}