「一本通 1.4 练习 3」移动玩具

题目描述

给定两个 $4 \times 4$ 的 01 矩阵（分别表示初始状态和目标状态，其中 1 表示有玩具，0 表示没有），保证两个矩阵中 1 的个数相同。每次操作可以选择上下或左右相邻的两个格子，若其中一个为 1、另一个为 0，则交换这两个格子的值。求将初始状态变为目标状态所需的最少操作次数。

思路

状态空间很小，用 16 位整数压缩 $4 \times 4$ 网格，枚举 24 对相邻格子进行状态转移，BFS 求最短路即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from collections import deque
from collections.abc import Iterator

# 相邻移动方向：上下左右在 16 位压缩状态下的位偏移与移动对
MOVES: list[tuple[int, int]] = (
    [(r * 4 + c, r * 4 + c + 1) for r in range(4) for c in range(3)]  # 横向相邻 12 对
    + [(r * 4 + c, (r + 1) * 4 + c) for r in range(3) for c in range(4)]  # 纵向相邻 12 对
)


def next_states(state: int) -> Iterator[int]:
    """产出当前状态经一次相邻格子移动（0 与 1 互换）后能达到的所有新状态。"""
    for u, v in MOVES:
        bit_u = (state >> u) & 1
        bit_v = (state >> v) & 1
        if bit_u != bit_v:
            yield state ^ (1 << u) ^ (1 << v)


def min_moves(start: int, target: int) -> int:
    """BFS 搜索从初始玩具状态到达目标状态所需的最少移动步数。"""
    if start == target:
        return 0

    dist: dict[int, int] = {start: 0}
    queue: deque[int] = deque([start])

    while queue:
        curr = queue.popleft()
        step = dist[curr]
        for nxt in next_states(curr):
            if nxt == target:
                return step + 1
            if nxt not in dist:
                dist[nxt] = step + 1
                queue.append(nxt)

    return -1


def parse_board(lines: list[str]) -> int:
    """将 4 行 01 字符串解析并压缩为一个 16 位的二进制整数。"""
    return sum(
        int(ch) << (r * 4 + c)
        for r, row in enumerate(lines)
        for c, ch in enumerate(row)
    )


def solve() -> None:
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    data = iter(tokens)
    start_lines = [next(data) for _ in range(4)]
    target_lines = [next(data) for _ in range(4)]
    start_state = parse_board(start_lines)
    target_state = parse_board(target_lines)
    print(min_moves(start_state, target_state))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:55
 * update_at: 2026-10-05 23:55
 */

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;

// 4x4 网格的 24 对相邻格子（位编号 0..15）
// 横向相邻：每行 3 对，共 4 行
// 纵向相邻：每列 3 对，共 4 列
const int MOVE_CNT = 24;
int mv_u[MOVE_CNT], mv_v[MOVE_CNT];

// dist[state] 表示从起点到该状态的最少步数，-1 表示未访问
int dist[1 << 16];

// 将 4 行 01 字符串压缩为 16 位整数，第 r 行第 c 列对应位 r*4+c
int parse_board() {
    int state = 0;
    for (int r = 0; r < 4; ++r) {
        string s;
        cin >> s;
        for (int c = 0; c < 4; ++c) {
            if (s[c] == '1') {
                state |= 1 << (r * 4 + c);
            }
        }
    }
    return state;
}

// BFS 求从 start 到 target 的最少移动步数
int bfs(int start, int target) {
    if (start == target) return 0;
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int step = dist[cur];
        for (int i = 0; i < MOVE_CNT; ++i) {
            int u = mv_u[i];
            int v = mv_v[i];
            int bu = (cur >> u) & 1;
            int bv = (cur >> v) & 1;
            if (bu == bv) continue; // 相同则交换无意义
            int nxt = cur ^ (1 << u) ^ (1 << v);
            if (nxt == target) return step + 1;
            if (dist[nxt] == -1) {
                dist[nxt] = step + 1;
                q.push(nxt);
            }
        }
    }
    return -1; // 题目保证可达
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理 24 对相邻格子
    int idx = 0;
    for (int r = 0; r < 4; ++r) {
        for (int c = 0; c < 3; ++c) {
            mv_u[idx] = r * 4 + c;
            mv_v[idx] = r * 4 + c + 1;
            ++idx;
        }
    }
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 4; ++c) {
            mv_u[idx] = r * 4 + c;
            mv_v[idx] = (r + 1) * 4 + c;
            ++idx;
        }
    }

    int start = parse_board();
    int target = parse_board();
    cout << bfs(start, target) << "\n";
    return 0;
}

「一本通 1.4 练习 3」移动玩具

目录

题目描述

思路

参考代码