外部BFS题，需要全局考虑，类似 845. 八数码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1 << 16;

int dist[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int input()                                     //将模式转换为二进制数
{
    int state = 0;
    for (int i = 0; i < 16; i ++ )
    {
        char c;
        cin >> c;
        if (c == '1') state += 1 << i;
    }

    return state;
}

void bit_swap(int &state, int x, int y)         //交换二进制数中的两位
{
    int a = state >> x & 1, b = state >> y & 1;
    state -= a << x, state -= b << y;
    state += a << y, state += b << x;
}

int bfs(int start, int end)
{
    if (start == end) return 0;

    queue<int> q;
    q.push(start);

    memset(dist, -1, sizeof dist);
    dist[start] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )           //枚举横纵坐标及方向
            for (int j = 0; j < 4; j ++ )
                for (int k = 0; k < 4; k ++ )
                {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < 4 && y >= 0 && y < 4)
                    {
                        int state = t;          //交换(i, j)和(x, y)两个格子中的棋子
                        bit_swap(state, i * 4 + j, x * 4 + y);

                        if (dist[state] == -1)
                        {
                            dist[state] = dist[t] + 1;
                            if (state == end) return dist[state];
                            q.push(state);
                        }
                    }
                }
    }

    return -1;
}

int main()
{
    int start = input();
    int end = input();

    cout << bfs(start, end) <<endl;

    return 0;
}