本题关键在于围成一圈的排列以及翻转运算如何表示。
从某处剪开形成线性排列是常用套路。具体从哪里剪开看处理方便。
由于初始位置是黑白各连续N个,用1表示黑,0表示白。标示2*N个位置分别为pos0,pos1,...,pos(2N-1)。令初始状态中,pos0~pos(N-1)为1(即黑色卡片),posN~pos(2N-1)为0(即白色卡片)。
从pos0和pos(2N-1)中间剪开,这个排列可以用一个2N比特的无符号整数{pos(2N-1}, pos(2N-2}, ... , pos0}表示,约定pos0为LSB,pos(2N-1}为MSB。
由此可得:
初始状态为0b000...0111...1 = 2**N-1
终止状态(黑白或01交错)有两种,分别是:0b1010...10, 0b010...101
在圆圈上翻转连续3张牌,可以用一个2*N比特的有3个比特为1的整数(称为掩码)与表示排列状态的整数进行按比特异或运算得到。
在每个状态下,“翻转连续3张牌”的可能位置有2*N种,对应的整数为7, 14, ...。但是要注意翻转位置跨越剪开的那个位置时的处理。比特数比较少的时候,用手动计算出掩码也是可以的。也可以找出规律用代码来实现(这样代码可扩展性更好)。本题解中用以下方式来求2*N种掩码:
(7<<k)对应于没有位宽限制时从7(0b111)出发的线性左移。求余部分代表没有移出2*N比特部分的值。移出的部分在循环左移中挪到了最右端,对应于以上整除部分。
基于以上讨论,这个问题就转化成了图搜索问题中的最短路径问题了,可以用广度优先搜索来解决。
算法流程如下:
# -*- coding: utf-8 -*-
"""
Created on Fri Oct 8 07:40:08 2021
@author: chenxy
"""
# import sys
import time
# import datetime
# import math
# import random
# from typing import List
# from queue import Queue
from collections import deque
# import itertools as it
# import numpy as np
N = 8
target1 = 0b1010_1010_1010_1010
target2 = 0b0101_0101_0101_0101
start = 0b0000_0000_1111_1111
mask = 2*N*[0]
for k in range(2*N):
mask[k] = (7 << k) // (2**16) + (7 << k) % (2**16)
step = 0
q = deque()
visited = set()
q.append((start,step))
visited.add(start)
while len(q) > 0:
cur,step = q.popleft()
# print('cur={0}, step={1}'.format(cur,step))
if cur == target1 or cur == target2:
break
for k in range(2*N):
nxt = cur ^ mask[k]
if nxt not in visited:
# print('\t{0}-->{1}'.format(cur,nxt))
q.append((nxt,step+1))
visited.add(nxt)
print('N = {0}, step = {1}'.format(N,step))
长假归来。。。Q48轻松搞定。呃,那一定是我的水平涨了嘛^-^老兵不死他只是慢慢凋零。。。