是的我又来水题解了

题目描述

在一个 $4 \times 4$ 的棋盘上有 $8$ 个黑棋和 $8$ 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。

移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

输入格式

第一行到第四行，每行 $4$ 个数字（$0$ 或者 $1$），描述了初始棋盘；

接着是一个空行；

第六行到第九行，每行 $4$ 个数字（$0$ 或者 $1$），描述了最终棋盘。

数字 $0$ 表示白棋，数字 $1$ 表示黑棋。

输出格式

输出一个整数，表示最少的移动步数。

输入样例

1111
0000
1110
0010

1010
0101
1010
0101

输出样例

4

算法

$bfs$

本题求最小步数，所以应当用 $bfs$ 来做。

我一开始居然在想状压dp

首先定义 $g$ 数组表示初始状态，$e$ 数组表示结束状态，$state$ 记录状态是否被遍历过，$dist$ 数组表示从 $g$ 开始的最小步数。

由于一个 $4 \times 4$ 的棋盘可以记录成一个长度为 $16$ 的数组，所以 $g$ 和 $e$ 都开成长度为 $16$ 的一维数组

如果遍历到了结束状态，那么返回步数，否则返回 $-1$，当然这并不可能。

由于 $state$ 的下标只能为整数，所以我们要考虑如何把一个 $16$ 位的 $bool$ 型数组不重不漏地转化为一个整数。

这才是难点

首先考虑像八数码一样全排列哈希，那么先算一下空间。

#include <stdio.h>

int main()
{
    long long res = 1;
    for (int i = 1; i <= 16; i ++ )
        res *= i;
    printf("%lld", res);
    return 0;
}

得到结果20922789888000（不用数了，$14$ 位），一般 $10 ^ 7$ 的数组就很极限了，真开到这么大就炸了，不可行。

考虑到每一个状态都是一个 $bool$ 型数组，正好可以不重复地对应一个二进制数，那么不妨考虑将其表示成二进制数。

算一下空间，每个状态有 $16$ 位，最大的一个状态为 $1111\ 1111\ 0000\ 0000$。二进制的 $8$ 个 $1$ 是 $255$，那么总空间就是 $256 \times 255$，$256 \times 255 < 256 \times 256 = 65536$，虽然有多余空间（比如 $0000\ 0000\ 0000\ 0001$ 就永远不会被用到），但已经可以接受了。

时间复杂度

$O(m)$，其中 $m$ 为状态数量。

$C++$ 代码实现

#include <stdio.h>

const int N = 16;
const int M = 65536;

bool g[N];// 初始状态
bool e[N];// 结束状态
bool state[M];// 每个状态是否被遍历过
int dist[M];// 最短距离
int q[M], hh, tt;// 广搜需要的队列

bool read_bool()// 这里使用快读是为了简化读入，每读入一个数字就会返回。用cin或scanf的话，会把4位读成一个数字
{
    char ch;
    do ch = getchar();
    while(ch == ' ' || ch == '\n');
    return ch == '1';
}

int hash(bool t[])// 将一个数组状态转化成一个数字状态
{
    int res = 0;
    for (int i = 0; i < 16; i ++ )
        res |= t[i] << i;
    return res;
}

int swp(int t, int a, int b)// 交换t的二进制中的第a位和第b位，并把交换后的结果返回
{
    int res = 0;// 记录返回的结果
    for (int i = 0; i < 16; i ++ )
        if (i == a)// 如果是第a位，那么把res的第a为制成t的第b位上的数
            res |= (t >> b & 1) << i;
        else if (i == b)// 如果是第b位，那么把res的第b位制成t的第a位上的数
            res |= (t >> a & 1) << i;
        else
            res |= (t >> i & 1) << i;// 如果不是以上两种情况，那就把t的第i位上的数复制到res的第i位上
    return res;
}

int bfs(int start, int end)// bfs里面所有状态都是二进制状态
{
    q[0] = start;// 初始状态入队
    state[start] = true;// 记录遍历过初始状态
    int dx[4] = {1, 0, -1, 0};// 向量
    int dy[4] = {0, 1, 0, -1};
    while (hh <= tt)// 当队列不空
    {
        int t = q[hh ++ ];// 取出对头
        if (t == end) return dist[t];// 如果到了终止状态，则返回
        for (int i = 0; i < 16; i ++ )// 枚举二进制中的16位
            if (t >> i & 1)// 如果第i为是1，即是黑棋，那么将其与四周交换
            {
                int x = i / 4, y = i % 4;// 求出坐标
                for (int j = 0; j < 4; j ++ )// 枚举四个向量
                {
                    int nx = x + dx[j], ny = y + dy[j];// 取出要交换的棋子坐标
                    if (nx < 4 && ny < 4 && nx >= 0 && ny >= 0)// 如果坐标在棋盘中
                    {
                        int k = nx * 4 + ny;// 算出要交换的棋子的二进制状态中的坐标
                        if (!(t >> k & 1))// 如果这个棋子也是黑棋，那么交换与不交换的状态都是一样的，避免dist[t]增加，将其特判不交换
                        {
                            int s = swp(t, i, k);// 用s记录交换后的二进制状态
                            if (!state[s])// 如果这个状态没有被遍历到
                            {
                                q[ ++ tt] = s;// 入队
                                state[s] = true;// 记录这个状态被遍历到了
                                dist[s] = dist[t] + 1;// s状态是从t状态转移过去的，所以到s的最短距离为到t的最远距离+1
                            }
                        }
                    }
                }
            }
    }
    return -1;// 如果没有到达终止状态，避免返回随机值，特判返回-1，虽然并不会被执行到
}

int main()
{
    for (int i = 0; i < 16; i ++ )// 快读处理输入
        g[i] = read_bool();
    for (int i = 0; i < 16; i ++ )
        e[i] = read_bool();
    printf("%d",bfs(hash(g), hash(e)));// 输出
    return 0;
}