自动搬运

查看原文

来自洛谷，原作者为

	Helenty 江风引雨 / 恣睢浇灭少年抱有的幻想 / 断弦声里 / 无计唤停没有结果的爆搜 / 此去经年 / 是否还能放下封存的回忆

搬运于2025-08-24 21:14:45，当前版本为作者最后更新于2025-03-12 10:43:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

给定一个十进制数 $x$，将它转换为二进制字符串并在高位填 $0$ 以补足 $16$ 位，就得到了一个长度为 $16$ 的 $01$ 字符串，我们用这个字符串表示 $4 ×4$ 的棋盘，按从左到右、从上到下的顺序将 $0$（白子）、$1$（黑子）放入棋盘。

我们现在可以交换棋盘中相邻（共享一条边的两个格子相邻，因此一个格子至多有 $4$ 个相邻的格子）的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下（右边棋盘所示）的棋盘，至少需要 $3$ 步。

对于给定的棋盘（保证棋盘中恰好有 $8$ 个白子和 $8$ 个黑子），求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。

看完题目，直接 BFS，因为这是“最少的交换步数”。

然后还要记得写一个“交换棋盘中两个位置的棋子状态”的函数，模块化编程，不然到了后面的代码都不知道自己在写什么。

“交换棋盘中两个位置的棋子状态”的函数具体如下：

• 提取二进制位的值；
• 判断是否需要交换；
• 交换二进制位的值；

解题代码

毕竟是本题的第一篇题解，所以就写点注释。

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; // 定义四个方向：上、下、左、右

int got(int x, int y) // 计算位置 (x, y) 在 16 位整数表示的棋盘中对应的二进制位索引
{
    return x * 4 + y;
}

int Swap(int state, int idx1, int idx2) // 交换棋盘中两个位置的棋子状态
{
    int bit1 = (state >> idx1) & 1; // 提取 idx1 位置的二进制位的值
    int bit2 = (state >> idx2) & 1; // 提取 idx2 位置的二进制位的值
    if (bit1 == bit2) return state; // 如果这两个位置的二进制位的值相同，说明棋子状态相同，无需交换，直接返回原状态
    state ^= (1 << idx1); // 使用异或运算将 idx1 位置的二进制位取反
    state ^= (1 << idx2); // 使用异或运算将 idx2 位置的二进制位取反
    return state; // 返回交换后的棋盘状态
}

int bfs(int step)
{
    queue<pair<int, int>> q;
    unordered_set<int> vis;
    q.push({step, 0});
    vis.insert(step);
    while (!q.empty())
	{
        auto [curState, curSteps] = q.front();
        q.pop();
        if (curState == 0x00FF) return curSteps; // 目标状态对应的整数，即前 8 位为 0，后 8 位为 1
        // 遍历棋盘每个位置
        for (int i = 0; i < 4; ++i)
		{
            for (int j = 0; j < 4; ++j)
			{
                int cur = got(i, j);
                for (int k = 0; k < 4; ++k)
				{
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < 4 && nj >= 0 && nj < 4) // 判断位置 (ni, nj) 是否在 4x4 棋盘内
					{
                        int next = Swap(curState, cur, got(ni, nj)); // 交换当前位置和相邻位置的棋子状态，得到新的棋盘状态
                        if (vis.find(next) == vis.end()) // 判断新的棋盘状态是否未被访问过
						{
                            q.push({next, curSteps + 1}); // 将新的棋盘状态和步数（当前步数加 1）加入队列
                            vis.insert(next); // 将新的棋盘状态标记为已访问
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int x;
    cin >> x;
    cout << bfs(x) << endl; // 输出答案 
    return 0;
}