思路

16位棋盘仅8黑8白，共12870可达状态；只交换异色相邻格，求最小步数而非输出方案。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){string s;int a=0,b=0;for(int i=0;i<8;i++){cin>>s;int &z=i<4?a:b;for(char c:s)z=z*2+c-'0';}vector<pair<int,int>>edges;for(int i=0;i<4;i++)for(int j=0;j<4;j++){int p=i*4+j;if(i<3)edges.push_back({p,p+4});if(j<3)edges.push_back({p,p+1});}vector<int>d(65536,-1);queue<int>q;d[a]=0;q.push(a);while(!q.empty()){int v=q.front();q.pop();if(v==b){cout<<d[v]<<'\n';return 0;}for(auto e:edges)if(((v>>e.first)&1)!=((v>>e.second)&1)){int z=v^(1<<e.first)^(1<<e.second);if(d[z]<0){d[z]=d[v]+1;q.push(z);}}}}