题解 P1225 【黑白棋游戏】

· · 题解

题意简述

求从一个 4\times4 的方阵变成另一个 4\times4 的方阵最少需要的步数以及步骤。 （棋子只能与相邻的棋子交换）

输入：

输出：

题目分析

这道题使用bfs。

搜索时注意交换 (a,b) 和 (a+1,b) 与 交换 (a+1,b) 和 (a,b) 是一样的效果，当枚举到 (a+1,b) 时再去与 (a,b) 交换就没有意义了，因为先枚举 (a,b)，如果能交换已经交换过了。(a,b) 与 (a,b+1) 也是同样的道理，所以我们可以得出结论，对于每个 (a,b) ，我们搜索时仅需与右边的和下面的进行交换。交换两个相同的数也没有意义，所以可以进行判断来省略。

因为棋盘只包含0和1，且只有16位，所以可以压缩成二进制方便储存。

比如说样例，将输入的两个方阵记为 a 和 b，则 a 可以压缩成 1111000011100010 即 61666。

我们可以通过 a & (1<<i) 来取得从左往右第 i 位的值，则它右边的值为 a & (1<<(i-1))，下面的值为 a & (1<<(i-4))。

为了记录操作，我们还需要知道第 i 位在原本的方阵中对应的坐标，它的纵坐标就是 \lfloor i\div4 \rfloor，横坐标即为 i\mod4。

由于要被交换的两位必定是一个0一个1，所以交换两位可以将这两位异或1

0\oplus1=1 1\oplus1=0

详情请见代码：

#include <bits/stdc++.h>
using namespace std;
struct record //用于记录步骤
{
    int x1;
    int y1;
    int x2;
    int y2;
};
struct status //每一个状态
{
    int num;            //方阵的二进制形式
    int t;              //需要的次数
    vector<record> rec; //记录步骤
};
status a, b;     //初始状态和目标状态
queue<status> q; //用于bfs
bool vis[66666]; //记录某个方阵是否被搜过
void bfs()
{
    q.push(a);
    while (!q.empty())
    {
        status tmp = q.front();
        q.pop();
        if (vis[tmp.num]) //如果搜到过那么就肯定不是最优解
        {
            continue;
        }
        vis[tmp.num] = 1;
        if (tmp.num == b.num) //如果与目标相同就输出
        {
            cout << tmp.t << endl;
            for (vector<record>::iterator it = tmp.rec.begin(); it != tmp.rec.end(); ++it)
            {
                cout << (it->x1) << (it->y1) << (it->x2) << (it->y2) << endl;
            }
            return;
        }
        for (int i = 15; i >= 0; --i) //枚举方阵每一位
        {
            /**
             * 15-i表示现在是方阵二进制的哪一位（从左到右）
             * (15-i) / 4 即 (15-i) >> 2 表示相当于原来的第几行
             * (15-i) % 4 即 (15-i) - (y << 2) 表示相当于原来的第几列
            */
            int y = (15 - i) >> 2;
            int x = (15 - i) - (y << 2);

            /*tmp.num & (1<<i) 表示当前方阵第i位，这里用aaa储存方便使用*/
            int aaa = 1 << i;

            status bbb; //临时储存下一个状态
            bbb.t = tmp.t + 1;
            bbb.rec = tmp.rec;

            /**
             * 左右交换
             * 限制 x<3 防止出界
             * 如果第i位与第i+1位相等就不用交换了
             * 第i+1位在10进制里对应的值就是第i位的值的一半
             * 因为这里的x和y是从0开始的，所以记录时要加一
             */
            bbb.num = tmp.num ^ aaa ^ (aaa >> 1);
            if (x < 3 and (tmp.num & aaa) ^ (tmp.num & (aaa >> 1)))
            {
                bbb.rec.push_back((record){y + 1, x + 1, y + 1, x + 2});
                q.push(bbb);
                bbb.rec.pop_back();
            }

            /**
             * 上下交换
             * 同上，不过这次是与下面的交换，需要右移一行即4位
             */
            bbb.num = tmp.num ^ aaa ^ (aaa >> 4);
            if (y < 3 and (tmp.num & aaa) ^ (tmp.num & (aaa >> 4)))
            {
                bbb.rec.push_back((record){y + 1, x + 1, y + 2, x + 1});
                q.push(bbb);
                bbb.rec.pop_back();
            }
        }
    }
}
int main()
{
    char ch;

    /*将读入的方阵变成二进制的形式并用int保存*/
    for (int i = 15; i >= 0; --i)
    {
        cin >> ch;
        a.num += (ch - '0') * (1 << i);
    }
    for (int i = 15; i >= 0; --i)
    {
        cin >> ch;
        b.num += (ch - '0') * (1 << i);
    }

    /*特判，如果一开始就相同那就不需要搜索了*/
    if (a.num == b.num)
    {
        cout << 0;
        return 0;
    }

    bfs();
    return 0;
}