题意分析

我们需要通过按压面板上的按钮，使得所有按钮的状态变为点亮。每个按钮的按压会根据给定的3x3模式切换周围按钮的状态。我们的目标是找到按压次数最少的按钮序列，并按照升序输出这些按钮的编号。如果无法点亮所有按钮，则输出"Impossible."。

解题思路

每个按钮的切换是异或操作，如果枚举所有的情况可能导致运算时间过长，考虑分治策略，将按钮分为两组，分别枚举每组的所有按压组合，并记录每组按压后的异或结果。

标程

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int r, c;
    int case_num = 1;
    while (cin >> r >> c) {
        if (r == 0 && c == 0) break;
        string pattern[3];
        for (int i = 0; i < 3; i++) {
            cin >> pattern[i];
        }

        int n = r * c;
        vector<int> mask_i(n, 0);

        for (int i = 0; i < n; i++) {
            int row = i / c;
            int col = i % c;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    int nr = row + dr;
                    int nc = col + dc;
                    if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
                        int pr = 1 + dr;
                        int pc = 1 + dc;
                        if (pr >= 0 && pr < 3 && pc >= 0 && pc < 3) {
                            if (pattern[pr][pc] == '*') {
                                int j = nr * c + nc;
                                mask_i[i] |= (1 << j);
                            }
                        }
                    }
                }
            }
        }

        int target = (1 << n) - 1;
        int half = n / 2;
        unordered_map<int, pair<int, int>> mapA;

        for (int mask_val = 0; mask_val < (1 << half); mask_val++) {
            int xorA = 0;
            int press_count = 0;
            for (int k = 0; k < half; k++) {
                if (mask_val & (1 << k)) {
                    press_count++;
                    xorA ^= mask_i[k];
                }
            }
            if (mapA.find(xorA) != mapA.end()) {
                pair<int, int> p = mapA[xorA];
                if (press_count < p.first || (press_count == p.first && mask_val < p.second)) {
                    mapA[xorA] = {press_count, mask_val};
                }
            } else {
                mapA[xorA] = {press_count, mask_val};
            }
        }

        int min_press = INT_MAX;
        int min_total_mask = -1;
        int rest = n - half;

        for (int mask_val = 0; mask_val < (1 << rest); mask_val++) {
            int xorB = 0;
            int press_count = 0;
            for (int k = 0; k < rest; k++) {
                if (mask_val & (1 << k)) {
                    press_count++;
                    xorB ^= mask_i[half + k];
                }
            }
            int need = target ^ xorB;
            if (mapA.find(need) != mapA.end()) {
                pair<int, int> p = mapA[need];
                int total_press = p.first + press_count;
                int total_mask = p.second | (mask_val << half);
                if (total_press < min_press || (total_press == min_press && total_mask < min_total_mask)) {
                    min_press = total_press;
                    min_total_mask = total_mask;
                }
            }
        }

        cout << "Case #" << case_num++ << endl;
        if (min_press == INT_MAX) {
            cout << "Impossible." << endl;
        } else {
            vector<int> buttons;
            for (int k = 0; k < n; k++) {
                if (min_total_mask & (1 << k)) {
                    buttons.push_back(k + 1);
                }
            }
            sort(buttons.begin(), buttons.end());
            for (int i = 0; i < buttons.size(); i++) {
                if (i > 0) cout << " ";
                cout << buttons[i];
            }
            cout << endl;
        }
    }
    return 0;
}