B3740 题解

· · 题解

解题思路

给定一个十进制数 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;
}