并不知道省选考这种爆搜题有什么意义。。
正文部分：
观察题目中只有12个数，每个数只有0和1，明显所以状态的数量为\(2^{12}=4096\)，那岂不是爆搜随便做？
对于1个状态hash:
我们将现在这12位数打包成一个字符串，用\(map\)记录一下这个字符串是否出现过。
对于1个状态的unhash,我们将这个字符串转到1个矩阵里，就是当前的状态。
于是我们就可以轻松的得到每种情况的状态。
对于Bfs过程，我们对unhash完的矩阵进行操作，每次选取其中为1的点，分4个方向向外扩散，然后压成1个新的状态，如此继续。
My Code:
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define il inline
#define gc getchar
using namespace std;
string S,T;
char x;
map<string,bool> vis;
int n,m,i,j,k;
int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int tmp[5][5];
struct Bfs {
string zt;int step;
};
il int read() {
int res = 0;char c;bool sign = 0;
for(c = gc();!isdigit(c);c = gc()) sign |= c == ‘-‘;
for(;isdigit(c);c = gc()) res = (res << 1) + (res << 3) + (c ^ 48);
return sign ? -res : res;
}
il void unhash(string s,int a[5][5]) {
int i,j,id = 0;
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
a[i][j] = s[id];id++;
}
}
return;
}
il string hash(int a[5][5]) {
int i,j;string res = "";
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
res += a[i][j];
}
}return res;
}
il void print(int a[5][5]) {
int i,j;
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
printf("%d%c",a[i][j],j == n ? ‘\n‘ : ‘ ‘);
}
}
}
il void bfs(string s,string t) {
queue<Bfs> Q;while(!Q.empty()) Q.pop();
Q.push((Bfs){s,0});vis[s] = 1;
while(!Q.empty()) {
string zt = Q.front().zt;int step = Q.front().step;
Q.pop();
if(zt == T) {
printf("%d",step);
exit(0);
}
unhash(zt,tmp);int i,j,k;
// print(tmp);
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
if(!tmp[i][j]) continue;
for(k = 0;k < 4;k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if(nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;
if(tmp[nx][ny]) continue;
tmp[nx][ny] = 1;tmp[i][j] = 0;
string new_zt = hash(tmp);
if(!vis[new_zt]) {
vis[new_zt] = 1;
Q.push((Bfs){new_zt,step + 1});
}
tmp[nx][ny] = 0;tmp[i][j] = 1;
}
}
}
}
}
int main() { S = T = "";
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
scanf("%c",&x);
while(!isdigit(x)) scanf("%c",&x);
S += x - 48;
}
}
for(i = 1;i <= 4;i++) {
for(j = 1;j <= 4;j++) {
scanf("%c",&x);
while(!isdigit(x)) scanf("%c",&x);
T += x - 48;
}
}
bfs(S,T);
return 0;
}