把 4×4 棋盘编码成 16 位掩码，相邻异色交换即两位同时翻转，在有限状态上跑 BFS 求最少步数。
OJ: roj
题目 ID: 1451
难度:普及
标签:BFS状态压缩
创建: 2026-09-30 11:24
更新: 2026-10-05 23:56
题目描述
4×4 棋盘上有 8 个黑棋（1）和 8 个白棋（0），每次可交换一对有公共边的相邻棋子。给出初始局面和目标局面（各为 4 行 01 串，中间空一行），求最少移动步数。
输入共 8 行 01 串，前 4 行为初始棋盘，后 4 行为目标棋盘，每行 4 个 0/1 数字；输出一行整数表示最少步数。
思路
局面总数为 C(16,8)=12870。把棋盘编码成 16 位整数，相邻异色交换等价于两位同时翻转，在状态图上跑 BFS 即可。
参考代码
Python 版：
python
#!/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-07-05 21:47
# update_at: 2026-07-05 21:47
import sys
from collections import deque
# 一对相邻格子编码为两个 16 位掩码：状态与这两格异或即完成一次交换
ADJ = (
[1 << (r * 4 + c) | 1 << (r * 4 + c + 1) for r in range(4) for c in range(3)] # 横向 12 对
+ [1 << (r * 4 + c) | 1 << ((r + 1) * 4 + c) for r in range(3) for c in range(4)] # 纵向 12 对
)
def board_of(row0: int, row1: int, row2: int, row3: int) -> int:
"""四行 01 数字各占 4 位、先读到的行占高位，拼成一个 16 位掩码。"""
return row0 << 12 | row1 << 8 | row2 << 4 | row3
def solve() -> None:
# 每行是 4 位 01 串（前导 0 有意义），按二进制解析；空行被 split 吞掉
lines = sys.stdin.buffer.read().split()
data = iter(int(line, 2) for line in lines)
start = board_of(next(data), next(data), next(data), next(data))
target = board_of(next(data), next(data), next(data), next(data))
dist = {start: 0} # start 出发的最短步数
q = deque([start])
while q and target not in dist:
u = q.popleft()
for pair in ADJ:
if u & pair in (0, pair):
continue # 两格同色，交换后局面不变
v = u ^ pair # 两格异色，交换 = 两位置同时翻转
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
print(dist[target])
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:56
* update_at: 2026-10-05 23:56
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
int dist[1 << 16]; // 每个 16 位掩码状态到起点的最短步数，-1 表示未访问
int pair_mask[24]; // 24 对相邻格子的掩码
int pm_cnt; // 相邻对数量
// 读取一个 4 位 01 串，cin >> s 会自动跳过空行和空白字符
int read_row() {
string s;
cin >> s;
return stoi(s, nullptr, 2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 预生成 24 对相邻格子的掩码：横向 12 对 + 纵向 12 对
pm_cnt = 0;
for (int r = 0; r < 4; ++r) {
for (int c = 0; c < 3; ++c) {
pair_mask[pm_cnt++] = (1 << (r * 4 + c)) | (1 << (r * 4 + c + 1));
}
}
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 4; ++c) {
pair_mask[pm_cnt++] = (1 << (r * 4 + c)) | (1 << ((r + 1) * 4 + c));
}
}
// 读入 8 个 4 位 01 串，前四个拼成初始状态，后四个拼成目标状态
int start = 0, target = 0;
for (int i = 0; i < 4; ++i) {
int row = read_row();
start = (start << 4) | row;
}
for (int i = 0; i < 4; ++i) {
int row = read_row();
target = (target << 4) | row;
}
// BFS：每条边代价为 1，第一次到达目标即为最少步数
memset(dist, -1, sizeof(dist));
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == target) break;
int d = dist[u];
for (int i = 0; i < pm_cnt; ++i) {
int p = pair_mask[i];
int sub = u & p;
if (sub == 0 || sub == p) continue; // 同色，交换不改变局面
int v = u ^ p; // 异色，交换等价于两格同时翻转
if (dist[v] == -1) {
dist[v] = d + 1;
q.push(v);
}
}
}
cout << dist[target] << "\n";
return 0;
}