如何不使用位集实现R行2列网格覆盖方案生成函数？

需求说明 #

我们需要实现一个函数：输入左列的障碍物分布（共R行，每行标记是否有障碍物），生成所有用1x1和2x2块覆盖左列剩余区域的方式，最终返回每种方式下右列被覆盖的行的状态集合。

原位运算代码逻辑回顾 #

原代码用整数的二进制位来表示每行状态：比如left_obstacles的第i位为1，代表左列第i行有障碍物。函数通过迭代尝试添加2x2块（每次覆盖连续两行的左右列），生成所有可能的左列覆盖状态对应的右列状态，最终收集所有右列状态。

无位运算实现思路 #

我们可以用布尔列表/元组替代位整数：每个长度为R的列表中，True表示对应行已被覆盖（障碍物或放置了块），False表示未覆盖。通过直接操作列表元素来检查、更新状态，完全避开位运算。

代码实现 #

def place22blocks_no_bitwise(left_obstacles_list):
    R = len(left_obstacles_list)
    # 初始状态：左列是给定的障碍物列表，右列全未覆盖
    options = set()
    # 列表转元组才能存入集合（元组可哈希）
    initial_left = tuple(left_obstacles_list)
    initial_right = tuple([False] * R)
    options.add((initial_left, initial_right))
    
    # 最多可放置R//2个2x2块，逐次尝试添加
    for _ in range(R // 2):
        new_options = set()
        for left_state, right_state in options:
            # 保留当前状态（不新增2x2块的情况）
            new_options.add((left_state, right_state))
            # 遍历所有可能的2x2块起始行
            for i in range(R - 1):
                # 检查左列连续两行是否都未被覆盖（无障碍物且未放块）
                if not left_state[i] and not left_state[i+1]:
                    # 更新左列状态：标记这两行为已覆盖
                    new_left = list(left_state)
                    new_left[i] = new_left[i+1] = True
                    new_left_tuple = tuple(new_left)
                    # 更新右列状态：同样标记这两行为已覆盖
                    new_right = list(right_state)
                    new_right[i] = new_right[i+1] = True
                    new_right_tuple = tuple(new_right)
                    # 将新状态加入集合
                    new_options.add((new_left_tuple, new_right_tuple))
        options = new_options
    
    # 提取所有右列状态，转成列表返回（也可保留元组）
    return [list(right) for right, _ in options]

关键细节说明 #

1. 用元组存状态：列表不可哈希，无法存入集合去重，所以把布尔列表转成元组来保存不同的状态组合。
2. 状态检查与更新：直接通过索引访问对应行的状态，判断是否能放2x2块；更新时复制原状态列表，修改对应行后再转成元组。
3. 与原输入对接：如果原输入是位集（整数），可以先转成布尔列表：

   # 示例：位集转布尔列表
   R = 4
   left_obstacles = 0b1010  # 第1、3行（从0开始计数）有障碍物
   left_obstacles_list = [(left_obstacles >> i) & 1 == 1 for i in range(R)]
   # 调用函数
   result = place22blocks_no_bitwise(left_obstacles_list)
   

内容的提问来源于stack exchange，提问作者user17977228