题目描述

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

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

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

样例

1111
0000
1110
0010

1010
0101
1010
0101

4

算法

(BFS外部搜索)

1. 这道题是BFS外部搜索，外部搜索的题一般分为以下几步：

   • 如何存储：1. 字符串string存储；2. 二进制来存储。(: 有知道怎么用string存储完整代码的大佬麻烦艾特我一下，我不太会。。
   • 将状态state放入一个队列中，可以是queue<string>，也可以是queue<int>，分别对应字符串存储和二进制存储
   • 进行判重，使用一个dis[]数组即可，如果是string存储的图，则使用map/unordered_map。二进制的话，使用一个int dist[N]即可。
   • 如何扩展：使用偏移量，从当前这个状态扩展到下一个状态，最终的答案就是从起点第一次搜到终点的时候
   • 如何更新扩展：3重循环，也许会重复枚举，但不会重复更新。一般每道题型的不同，只有存储和扩展不太一样。

2. 算法实现第一步：将棋盘读入，把整个棋盘转化为一个状态state，state就是一个int型整数。初始状态是queue<int> q, q.push(start)
3. 进入while(q,size())后，就是扩展部分，该题扩展的本质是——枚举一下交换哪两个格子，枚举3重循环。if(x>0 ... y < n)这个成立，所以该方向是有格子的，那么就交换(i, j)和(x, y)这两个格子。(i, j)表示当前状态state下的一个格子，(x, y)表示当前状态state下的另一个格子。队列中的队首元素q.front()，也就是t，就表示当前状态，一个二进制位表示的状态，该状态的体现是一个int型整数。
4. bit_swap()函数要好好品一下。
5. input()函数一开始写错了，已经改正。
6. if(dist[state] == -1)是执行的条件，一开始写成if(dist[state] != -1)了。有一点要注意：if(dist[state] == -1)和if(x >= 0 && x < 4 && y >= 0 && y < 4)这两个条件不能合并在一起，要先判断if(x >= 0 && x < 4 && y >= 0 && y < 4)，然后计算state，再进行if(dist[state] == -1)的判断
7. 我对input()函数中的cin是如何区分st和ed的字符的时候，一直没太懂，cin碰到换行后没字符就返回false嘛？而且为什么input()函数中读入的要是字符char，而不能是int?

时间复杂度

$O(12870 * 4 * 4 * 4)$
合法状态一共有12870个，组合数C16-8就可以
枚举行数为4，列数为4，方向有4个。
总结：这个算法一共会有12870个不同的合法状态，每个状态只会枚举16个格子，每个格子枚举上下左右4个方向。
不同的状态取决于哪些位置放黑棋，哪些位置放白棋，一共16个位置，有8个黑棋，所以是C16 8

C++ 代码

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

using namespace std;

const int N = 1 << 16;

// int state;
int dist[N];  // **1


int input()
{
    int state = 0;

    // for(int i = 0; i < 4; i ++)  // **3
    for(int i = 0; i < 16; i ++)
    {
        /*
        int x;
        cin >> x;
        */

        char c;
        cin >> c;

        // if(x == 1) state = 1 << i;   // **4
        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 st, int ed)
{
    if(st == ed) return 0;

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

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

    // int state = st;     // **1

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    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;
                        bit_swap(state, i * 4 + j, x * 4 + y);

                        if(dist[state] == -1)    // **2
                        {
                            dist[state] = dist[t] + 1;
                            if(state == ed) return dist[state];
                            q.push(state);
                        }
                    }
                }
    }

    return 0;
}


int main()
{
    int st = input();
    int ed = input();

    cout << bfs(st, ed) << endl;

    return 0;
}