题意分析

• 游戏规则：在 4×4 棋盘上，每个格子是双面棋子（w 或 b 朝上）。每轮选一个棋子，翻转该棋子及其上下左右相邻棋子（若存在），每次翻转 3 - 5 个棋子，目标是用最少轮次让所有棋子同色（全 w 或全 b ）。
• 输入输出：输入 4 行、每行 4 个字符表示初始棋盘；输出最少轮次，无法达成则输出 Impossible，已达成则输出 0 。

解题思路

这是典型的广度优先搜索（BFS） 问题，核心思路如下：

1. 状态表示：用 16 位无符号短整型 round_status 表示棋盘状态，每一位对应一个棋子，1 代表 b，0 代表 w，压缩状态便于存储和遍历。
2. 初始状态：读取输入，转换为对应的 round_status ，检查是否已满足全同色，满足则直接输出 0 。
3. 状态转移：对每个状态，尝试翻转 4×4 棋盘中每个位置的棋子（即模拟每轮操作），生成新状态。
4. 广度优先搜索：用队列存储待探索状态，记录每个状态的步数。遍历过程中，标记已访问状态（used 数组）避免重复探索，若遇到全同色状态，返回当前步数。若队列空仍未找到，输出 Impossible 。

#include <iostream>
#include <cstring>
using namespace std;

const int BOARD_SIZE = 4;
const int MAX_STATES = 65536;

typedef unsigned short State;

bool visited[MAX_STATES];

// 检查状态是否为全白或全黑
bool isGoal(State state) {
    return state == 0 || state == 0xFFFF;
}

// 翻转指定位置及其相邻位置
State flip(State state, int x, int y) {
    int pos = x * BOARD_SIZE + y;
    State mask = 1 << pos;
    
    // 上
    if (x > 0) mask |= 1 << ((x-1) * BOARD_SIZE + y);
    // 下
    if (x < BOARD_SIZE-1) mask |= 1 << ((x+1) * BOARD_SIZE + y);
    // 左
    if (y > 0) mask |= 1 << (x * BOARD_SIZE + y - 1);
    // 右
    if (y < BOARD_SIZE-1) mask |= 1 << (x * BOARD_SIZE + y + 1);
    
    return state ^ mask;
}

// BFS求解最小步数
int bfs(State initial) {
    if (isGoal(initial)) return 0;
    
    State queue[MAX_STATES];
    int step[MAX_STATES];
    int head = 0, tail = 0;
    
    memset(visited, false, sizeof(visited));
    
    queue[tail] = initial;
    step[tail] = 0;
    visited[initial] = true;
    tail++;
    
    while (head < tail) {
        State current = queue[head];
        int currentStep = step[head];
        head++;
        
        // 尝试所有可能的翻转
        for (int x = 0; x < BOARD_SIZE; x++) {
            for (int y = 0; y < BOARD_SIZE; y++) {
                State next = flip(current, x, y);
                
                if (isGoal(next)) return currentStep + 1;
                
                if (!visited[next]) {
                    visited[next] = true;
                    queue[tail] = next;
                    step[tail] = currentStep + 1;
                    tail++;
                    
                    if (tail >= MAX_STATES) return -1; // 理论上不会发生
                }
            }
        }
    }
    
    return -1; // 无法达成
}

int main() {
    State initial = 0;
    
    // 读取输入
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            char c;
            cin >> c;
            if (c == 'b') {
                initial |= (1 << (i * BOARD_SIZE + j));
            }
        }
    }
    
    // 求解
    int result = bfs(initial);
    
    // 输出结果
    if (result == -1) {
        cout << "Impossible" << endl;
    } else {
        cout << result << endl;
    }
    
    return 0;
}

该程序使用广度优先搜索（BFS）遍历所有可能的状态，确保找到的是最小步数。状态用16位无符号整数表示，每一位对应棋盘上的一个位置。通过位运算高效处理翻转操作，利用哈希表（visited数组）记录已访问状态以避免重复计算。