T24390: 黑白棋子

bitmask, bfs, http://cs101.openjudge.cn/practice/24390/

N枚棋子排成一排，其中有黑子也有白子。

你可以任意选择一枚棋子释放魔法，这个魔法会让该棋子和与它相邻的棋子一起改变颜色（黑变白，白变黑）。

给定初始时每个棋子的颜色，请你计算最少释放几次魔法，可以让所有棋子颜色变一致。

输入

第一行包含一个整数N。第二行包含长度为N的01串，代表棋子的颜色。0代表黑子，1代表白字。

1 <= N <= 20

输出

一个整数代表答案

样例输入

5
01101

样例输出

提示

输入保证可以做到所有棋子颜色变一致。

来源

张老师和杜老师编程课

这是一个 最小操作数使序列全相同 的问题，操作规则是「翻转一个点及其相邻点」。

约束条件：N ≤ 20，规模很小，可以用 状态搜索 / 枚举 来做。

思路解析

状态表示 用一个长度为 (N) 的 01 串表示当前棋子颜色。操作就是对某个位置 (i) 做 flip(i)：
- 翻转 (i)，以及 (i-1)、(i+1)（如果存在）。
目标变成全 0（全黑）或全 1（全白）。
算法选择
- N ≤ 20，所有可能状态最多 (2^{20} = 1,048,576)，完全可行。
- 可以用 BFS（最少步数）从初始状态出发，直到到达目标状态。

Python 实现

python

from collections import deque


def solve():
    N = int(input().strip())
    s = input().strip()

    # 初始状态转成整数（二进制掩码）
    start = int(s, 2)
    print(f"start = {start}")
    target1 = 0  # 全 0
    target2 = (1 << N) - 1  # 全 1

    # 预先计算每个位置的翻转掩码
    masks = []
    for i in range(N):
        mask = 1 << i
        if i > 0:
            mask |= 1 << (i - 1)
        if i < N - 1:
            mask |= 1 << (i + 1)
        masks.append(mask)

    # BFS
    q = deque([(start, 0)])
    visited = {start}

    while q:
        state, step = q.popleft()
        if state == target1 or state == target2:
            print(step)
            return
        for mask in masks:
            nxt = state ^ mask  # 翻转操作，就是「0→1，1→0」，等价于 XOR 1
            if nxt not in visited:
                visited.add(nxt)
                q.append((nxt, step + 1))


if __name__ == "__main__":
    solve()

T24390: 黑白棋子 ​

T24390: 黑白棋子