机关

GitHub跳转原题关系图返回列表

把 12 个四进制旋钮压成整数，正反生成状态做双向 BFS 并恢复最短操作序列。

OJ: luogu

题目 ID: P5507

难度:提高+/省选-

标签:双向BFS状态压缩路径恢复python

日期: 2026-07-16 20:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

12 个旋钮各有 4 个状态。旋转某旋钮会按它旋转前的状态联动另一个旋钮，求到全 1 状态的最少操作并输出方案。

思路

每个旋钮用 2 位，整个机关压入 24 位整数。正向边容易生成；反向枚举操作 i 时，先推回旋钮 i 的旧状态，由旧状态确定当时被联动的旋钮，再把两者各逆转一次。

从初态和目标分别 BFS，每次扩展较小前沿。起点侧记录 (前驱, 操作)，目标侧反搜时记录 (后继, 正向操作)；相遇后两段即可恢复完整方案。

Python 知识

  • Python 整数的位清除与置位可原地更新某个 2 位字段。
  • set 保存当前 BFS 前沿，字典同时保存访问状态和父指针。
  • 正向与反向函数分开写，便于独立模拟验证构造答案。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
initial = 0
trigger = []
for knob in range(12):
    state = next(data) - 1
    initial |= state << (2 * knob)
    trigger.append(tuple(next(data) - 1 for _ in range(4)))


def change(state, knob, delta):
    shift = 2 * knob
    value = ((state >> shift) + delta) & 3
    return state & ~(3 << shift) | value << shift


def forward(state, knob):
    selected_state = state >> (2 * knob) & 3
    affected = trigger[knob][selected_state]
    return change(change(state, knob, 1), affected, 1)


def backward(state, knob):
    previous_selected = ((state >> (2 * knob)) - 1) & 3
    affected = trigger[knob][previous_selected]
    return change(change(state, knob, -1), affected, -1)


from_start = {initial: (-1, -1)}
to_goal = {0: (-1, -1)}
start_frontier = {initial}
goal_frontier = {0}
meeting = initial if initial == 0 else None

while meeting is None:
    if len(start_frontier) <= len(goal_frontier):
        next_frontier = set()
        for state in start_frontier:
            for knob in range(12):
                next_state = forward(state, knob)
                if next_state in from_start:
                    continue
                from_start[next_state] = state, knob
                next_frontier.add(next_state)
                if next_state in to_goal:
                    meeting = next_state
                    break
            if meeting is not None:
                break
        start_frontier = next_frontier
    else:
        next_frontier = set()
        for state in goal_frontier:
            for knob in range(12):
                previous_state = backward(state, knob)
                if previous_state in to_goal:
                    continue
                to_goal[previous_state] = state, knob
                next_frontier.add(previous_state)
                if previous_state in from_start:
                    meeting = previous_state
                    break
            if meeting is not None:
                break
        goal_frontier = next_frontier

answer = []
state = meeting
while from_start[state][0] != -1:
    state, knob = from_start[state]
    answer.append(knob + 1)
answer.reverse()
state = meeting
while to_goal[state][0] != -1:
    state, knob = to_goal[state]
    answer.append(knob + 1)

print(len(answer))
print(*answer)

复杂度

总状态上限 4124^{12}，双向 BFS 通常只访问其中很小一部分；空间与访问状态数同阶。

总结

构造题的样例答案不唯一，应验证“步数最短 + 操作模拟到目标”，不能用纯文本相等判断正确性。