移动玩具

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1539 字
状压 BFS 枚举玩具移向相邻空位
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1453
// 题意：4 * 4 方框里有若干相同玩具，每次可以把一个玩具移到上下左右相邻的空位，求变到目标状态的最少移动次数。
// 思路：状态压缩 BFS。
// 1. 16 个格子用一个 16 位二进制表示，1 表示有玩具。
// 2. 一步操作是：选一个有玩具的格子，把它移到相邻的空位上。
// 3. 状态总数 65536，BFS 一次跑完，第一次到达目标即最少步数。
// 复杂度：O(2^16 * 16) 时间 / O(2^16) 空间
// 易错点：移动的目标格子必须是空的，判断条件是目标位为 0，否则会把两个玩具叠在一起。
// 易错点：输入的 8 行里前 4 行是初始状态、后 4 行是目标状态，中间的空行用 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[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    while(!q.empty()){
        int s = q.front();
        q.pop();
        if(s == target) break;
        for(int i = 0; i < 16; i++){
            if(!((s >> i) & 1)) continue;
            int r = i / 4, c = i % 4;
            for(int k = 0; k < 4; k++){
                int nr = r + dr[k], nc = c + dc[k];
                if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
                int j = nr * 4 + nc;
                if((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;
}
移动玩具

正文

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