状压bfs

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 65536;
int s,t,dis[maxn],dx[4] = {-4 , -1 , 1 , 4},ans[maxn][2],cnt;
void bfs(){
	memset(dis , -1 , sizeof dis);	
	queue <int> q;
	dis[s] = 0;
	q.push(s);
	while (!q.empty()){
		int x = q.front(),nx,k;
//        cout << x << '\n';
		q.pop();
		for (int i = 0;i < 16;i++){
			for (int j = 0;j < 4;j++){
				k = i + dx[j];
				if (k < 0 || k > 15) continue;
				if (((x >> i) & 1) != 1 || ((x >> k) & 1) != 0) continue;
				nx = x ^ ((1 << i) + (1 << k));
				if (dis[nx] != -1) continue;
				dis[nx] = dis[x] + 1;
				q.push(nx);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for (int i = 1;i <= 16;i++){
		char c;
		cin >> c;
		s = s * 2 + c - '0';
	}
	for (int i = 1;i <= 16;i++){
		char c;
		cin >> c;
		t = t * 2 + c - '0';
	}
	bfs();
	cout << dis[t] << endl;
	return 0;
}