发现地图仅 $4 * 4$，最多 $2^{16} = 65536$ 种状态，于是直接对状态进行 BFS。

利用 std::bitset 压位更好实现。

AC Code

#include <bits/stdc++.h>

struct Martix {
    constexpr static size_t _convert(int x, int y) { return x*4+y;}

    std::bitset<16> data;

    // 包装一层，防止主程序内编码出错（运行时内联，实际 0 开支）
    void update(int raw, bool status) { data.set(raw, status); } 
    void update(int x, int y, bool status) { data.set(_convert(x, y), status); }
    bool get(int x, int y) const { return data.test(_convert(x, y)); }

    // 使用 `std::unordered_map` / `std::unordered_set` 时，`Key` 需要支持 == 函数，这里直接使用 `std::bitset::operator ==()`。
    bool operator==(Martix const &rhs) const { return data == rhs.data; }
    // 隐式转化为 `std::bitset<16>`，用于 `std::hash`
    operator const std::bitset<16> &() const { return data; }
};

// 使用 `std::unordered_map` / `std::unordered_set` 时，`Key` 需要有 `std::hash<Key>` 特化，
// 这里 `Martix` 实际是 `std::bitset<16>` 的包装，这里直接使用 `std::bitset<16>` 的 `std::hash` 特化。
template <> struct std::hash<Martix>: public std::hash<std::bitset<16>> {};

constexpr int8_t dxy[][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

int main() {
    Martix source, target;

    for(Martix *const pmtx: {&source, &target}) {
        for(int i = 0; i < 16; ++i) {
            char ch = getchar();
            while(ch != '0' && ch != '1') ch = getchar();
            pmtx->update(i, ch == '1');
        }
    }

    std::queue<std::pair<Martix, int>> Q;
    Q.emplace(source, 0);

    // 哈希表维护（实际使用数组也可，因为仅 65536 状态）
    std::unordered_map<Martix, int> mp;
    mp.emplace(source, 0);

    while(!Q.empty()) {
        auto const [mtx, step] = Q.front(); Q.pop();

        if(mtx == target) break;

        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j)
                if(mtx.get(i, j))
                    for(auto const[dx, dy]: dxy) {
                        int const nx = i + dx, ny = j + dy;

                        if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4) continue;
                        if(mtx.get(nx, ny)) continue;

                        Martix newMtx = mtx;
                        newMtx.update(i, j, false), newMtx.update(nx, ny, true);

                        if(mp.emplace(newMtx, step + 1).second)
                            Q.emplace(newMtx, step + 1);
                    }
    }

    std::cout << mp[target];
}

https://blog.csdn.net/tenkuo/article/details/153832212

/*
将：
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

压缩成：
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
的二进制数 

对应着 2 的：
15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
次方位的 1 

那么 6号位 想要往上移动，对应的 2 次方 10 就得 +4 变成 14，对应 2 号位
		   想要往下移动，对应的 2 次方 10 就得 -4 变成 6，对应 10 号位
		   想要往左移动，对应的 2 次方 10 就得 +1 变成 11，对应 5 号位
		   想要往右移动，对应的 2 次方 10 就得 -1 变成 9，对应 7 号位
		   
当然移动前还要看看这些位置有没有玩具，是不是边界 
*/
#include<bits/stdc++.h>
using namespace std;

int st, ed;
map<int, bool> mp;

struct State {
	int s;   // 二进制状态 
	int k;   // 当前移动次数 
}; 

int get_ans() {
	queue<State> Q;
	Q.push({st, 0});   // 初始移动次数为 0 
	mp.clear();
	 
	while (!Q.empty()) {
		State x = Q.front(); Q.pop();
		if (mp[x.s]) {
			continue;
		}
		mp[x.s] = 1;
		if (x.s == ed) {
			return x.k;
		}
		
		for (int i = 0; i < 16; i ++) if ( (1 << i) & x.s ){
			// 找 x.s 状态上有的 1 
			// ***注意，当前 i 是二进制位上有的 1，也就是上面说的 0 ~ 15
			// 要把 0 ~ 15 映射回去，再移动和判断边界 
			 
			if (i + 4 < 16 && !( (1 << (i + 4)) & x.s ) && i / 4  != 3) {
				// 当前 1 的正上方有空位（0） 并且 i 代表的位置不在最上面一行 
				// ***这里的意思是，最上面一行映射的二进制次方 / 4 都为 3 
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i + 4));
				// 将当前第 i 位的 1 转移到正上方 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i - 4 >= 0 && !( (1 << (i - 4)) & x.s ) && i / 4 != 0) {
				// 当前 1 的正下方有空位（0） 并且 i 代表的位置不在最下面一行 
				// ***这里的意思是，最下面一行映射的二进制次方 / 4 都为 0
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i - 4));
				// 将当前第 i 位的 1 转移到正下方 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i + 1 < 16 && !( (1 << (i + 1)) & x.s ) && i % 4 != 3) {
				// 当前 1 的左边有空位（0） 并且 i 代表的位置不在最左边一列 
				// ***这里的意思是，最左边一列映射的二进制次方 % 4 都为 3 
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i + 1));
				// 将当前第 i 位的 1 转移到左边 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i - 1 >= 0 && !( (1 << (i - 1)) & x.s ) && i % 4!= 0) {
				// 当前 1 的右边有空位（0） 并且 i 代表的位置不在最右边一列 
				// ***这里的意思是，最右边一列映射的二进制次方 % 4 都为 0
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i - 1));
				// 将当前第 i 位的 1 转移到右边 
				Q.push({new_s, x.k + 1}); 
			} 
		}
	}
	
	return 0;   // 不可能到这，但还是写一个 
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	st = 0;   // 一定要记得初始化！！ 
	for (int i = 1; i <= 4; i ++) {
		char s[10];   // 需要开大点，不然会有奇怪的错误 
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			st = (st << 1) + (s[j] - '0');   
			// 相当于把现有的都往前移一位，给当前 0 / 1 空出位置 
		}
	}
	
	ed = 0;   // 这里也是 
	for (int i = 1; i <= 4; i ++) {
		char s[10];
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			ed = (ed << 1) + (s[j] - '0');
		}
	}
	
	cout << get_ans() << "\n";
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int s, step;
    node(){}
    node(int ss=0, int p=0)
    {
        s=ss;
        step=p;
    }
};
int st, ed; bool v[65537];
queue<node> q;
int main()
{
    for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)
    {
        int x;scanf("%1d", &x);
        st<<=1;
        st+=x;
    }
    for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)
    {
        int x;scanf("%1d", &x);
        ed<<=1;
        ed+=x;
    }
    q.push(node(st, 0));
    memset(v,0,sizeof(v));v[st]=True;
    while(q.size())
    {
        node no=q.front();q.pop();
        if(no.s==ed){printf("%d",no.step);break;}
        for(int i=0;i<4;i++)for(int j=0;j<4;j++)
        {
            if(i+1<4)
            {
                bool x=no.s & (1 << (4 * i + j));
                bool y=no.s & (1 << (4 * i + 4 + j));
                if(x!=y)
                {
                    node tno=no;tno.step++;
                    tno.s^= (1 << (4 * i + j));
                    tno.s^= (1 << (4 * i + 4 + j));
                    if(!v[tno.s])
                    {
                        v[tno.s]=True;
                        q.push(tno);
                    }
                }
            }
            if(j+1<4)
            {
                bool x=no.s & (1 << (4 * i + j));
                bool y=no.s & (1 << (4 * i + j + 1));
                if(x!=y)
                {
                    node tno=no;tno.step++;
                    tno.s^= (1 << (4 * i + j));
                    tno.s^= (1 << (4 * i + j + 1));
                    if(!v[tno.s])
                    {
                        v[tno.s]=True;
                        q.push(tno);
                    }
                }
            }

        }
    }
    return 0;
}