棋盘游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1503 字
状压 BFS 枚举相邻异色棋子的交换
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1451
// 题意：4 * 4 棋盘上 8 个黑棋 8 个白棋，每次可以交换相邻的两个棋子，求从初始棋盘变到目标棋盘的最少交换次数。
// 思路：状态压缩 BFS。
// 1. 棋盘只有 16 格，用 16 位二进制表示一个状态（1 为黑棋）。
// 2. 一步操作就是交换一对相邻且颜色不同的棋子，枚举每个格子的右邻和下邻即可覆盖全部相邻对。
// 3. 状态总数 C(16, 8) = 12870，BFS 一次跑完。
// 复杂度：O(2^16 * 16) 时间 / O(2^16) 空间
// 易错点：只能交换颜色不同的相邻棋子，交换同色的两个格子不产生新状态，要跳过。
// 易错点：输入是连续 8 行 01 串（中间夹一个空行），用 cin 读字符串会自动跳过空行，不要按字符逐个读。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int start = 0, target = 0;
    for(int i = 0; i < 8; i++){
        string s;
        if(!(cin >> s)) return 0;
        for(char ch : s){
            if(i < 4) start = start * 2 + (ch - '0');
            else target = target * 2 + (ch - '0');
        }
    }
    vector<int> dis(1 << 16, -1);
    queue<int> q;
    dis[start] = 0;
    q.push(start);
    int dr[2] = {0, 1};
    int dc[2] = {1, 0};
    while(!q.empty()){
        int s = q.front();
        q.pop();
        if(s == target) break;
        for(int i = 0; i < 16; i++){
            int r = i / 4, c = i % 4;
            for(int k = 0; k < 2; k++){
                int nr = r + dr[k], nc = c + dc[k];
                if(nr >= 4 || nc >= 4) continue;
                int j = nr * 4 + nc;
                if(((s >> i) & 1) == ((s >> j) & 1)) continue;
                int t = s ^ (1 << i) ^ (1 << j);
                if(dis[t] < 0){
                    dis[t] = dis[s] + 1;
                    q.push(t);
                }
            }
        }
    }
    cout << dis[target] << "\n";
    return 0;
}
棋盘游戏

正文

一本通·提高篇的其它内容
