本文共 2536 字，大约阅读时间需要 8 分钟。
为了解决这个问题，我们需要找到将4x4方格翻转为全白或全黑所需的最少步骤数。每次操作可以选择一个棋子，并翻转它及其周围的棋子（如果有的话）。我们可以使用广度优先搜索（BFS）来找到最短路径，因为BFS可以有效地找到最少的步骤数。
import sysfrom collections import dequedef 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") returnif __name__ == "__main__": main() 转载地址：http://fdxfk.baihongyu.com/