本文共 2594 字，大约阅读时间需要 8 分钟。

为了解决这个问题，我们需要找到将4x4方格翻转为全白或全黑所需的最少步骤数。每次操作可以选择一个棋子，并翻转它及其周围的棋子（如果有的话）。我们可以使用广度优先搜索（BFS）来找到最短路径，因为BFS可以有效地找到最少的步骤数。

方法思路

解决代码

import sys
from collections import deque
def main():
    # 读取输入并构建初始状态
    grid = []
    for _ in range(4):
        line = sys.stdin.readline().strip()
        grid.append([1 if c == 'b' else 0 for c in line])
    
    # 检查初始状态是否已经是全白或全黑
    all_zero = all(cell == 0 for row in grid for cell in row)
    all_one = all(cell == 1 for row in grid for cell in row)
    if all_zero or all_one:
        print(0)
        return
    
    # BFS初始化
    visited = set()
    queue = deque()
    initial_state = tuple(tuple(row) for row in grid)
    queue.append((initial_state, 0))
    visited.add(initial_state)
    
    # 目标检查函数
    def is_goal(state):
        return all(cell == 0 for row in state for cell in row) or all(cell == 1 for row in state for cell in row)
    
    while queue:
        current_state, steps = queue.popleft()
        if is_goal(current_state):
            print(steps)
            return
        
        # 生成所有可能的下一步操作
        for i in range(4):
            for j in range(4):
                # 生成delta矩阵
                delta = [[0]*4 for _ in range(4)]
                if i > 0:
                    delta[i-1][j] ^= 1
                if i < 3:
                    delta[i+1][j] ^= 1
                if j > 0:
                    delta[i][j-1] ^= 1
                if j < 3:
                    delta[i][j+1] ^= 1
                delta[i][j] ^= 1
                
                # 生成新状态
                new_state = []
                for x in range(4):
                    row = []
                    for y in range(4):
                        row.append(current_state[x][y] ^ delta[x][y])
                    new_state.append(row)
                new_state = tuple(tuple(row) for row in new_state)
                
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, steps + 1))
        
        # 如果队列为空，无法找到解
        if not queue:
            print("Impossible")
            return
if __name__ == "__main__":
    main()

代码解释

转载地址：http://fdxfk.baihongyu.com/