这是一个经典的“十字翻转”问题，我们可以通过**状态递推**结合**枚举首行**的方法来高效求解。由于 m 最大为 15，我们可以枚举首行的所有可能状态（共 \(2^{15}=32768\) 种），然后通过首行递推出后续所有行的状态，最后验证末行是否满足条件即可。

解题思路

1. 问题建模：将“翻转十字”转化为线性方程组问题。每个位置的最终状态由其自身及上下左右的翻转操作决定（异或运算）。
2. 首行枚举：由于 m ≤ 15，首行共有 \(2^m\) 种可能。我们按“方案值”（首行逆序的二进制值）从小到大枚举首行。
3. 状态递推：确定首行后，后续每一行的状态可由前一行唯一确定（为了让前一行全为黑）。
4. 验证末行：递推完所有行后，检查末行是否满足全黑条件。若满足，则为一个合法解。

C++ 实现代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<vector<int>>> solutions;
    int total = 0;

    // 枚举首行的所有可能状态（按方案值从小到大）
    for (int s = 0; s < (1 << m); ++s) {
        // 1. 生成逆序的首行（rev_row0），再逆序得到原首行 row0
        vector<int> rev_row0(m);
        for (int k = 0; k < m; ++k) {
            rev_row0[k] = (s >> (m - 1 - k)) & 1;
        }
        vector<int> row0(m);
        for (int j = 0; j < m; ++j) {
            row0[j] = rev_row0[m - 1 - j];
        }

        // 2. 初始化翻转矩阵 x
        vector<vector<int>> x(n, vector<int>(m, 0));
        for (int j = 0; j < m; ++j) {
            x[0][j] = row0[j];
        }

        // 3. 递推计算后续每一行的状态
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < m; ++j) {
                int term = 1;
                term ^= x[i][j];
                if (i > 0) term ^= x[i-1][j];
                if (j > 0) term ^= x[i][j-1];
                if (j < m-1) term ^= x[i][j+1];
                x[i+1][j] = term;
            }
        }

        // 4. 验证最后一行是否合法
        bool valid = true;
        for (int j = 0; j < m; ++j) {
            int left = x[n-1][j];
            if (n >= 2) left ^= x[n-2][j];
            if (j > 0) left ^= x[n-1][j-1];
            if (j < m-1) left ^= x[n-1][j+1];
            if (left != 1) {
                valid = false;
                break;
            }
        }

        if (valid) {
            total++;
            if (solutions.size() < 10) {
                solutions.push_back(x);
            }
        }
    }

    // 输出结果
    if (total == 0) {
        cout << "Impossible\n";
    } else {
        for (int k = 0; k < solutions.size(); ++k) {
            if (k > 0) {
                cout << "\n"; // 方案之间的空行
            }
            cout << k + 1 << "\n";
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    cout << solutions[k][i][j] << " ";
                }
                cout << "\n";
            }
        }
        cout << "\n" << total << "\n";
    }

    return 0;
}

http://www.gensokyo.red/?p=629

\(\sum a_{i} a + b + c\)

既然是水题我就不写了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：81ms

此题n=100- -

不看题解不知道交了4遍才A

仅仅是数组开小了 = =。。

这题是位运算很好的练手题阿

贴个matrix67大牛位运算的教程

http://www.matrix67.com/blog/archives/122

什么垃圾数据，数组到20还不过，开了100总算过了！！~~！！~！！~，垃圾的应该是描述吧呵呵

和费解的开关差不多……

什么破数据。。。

■■□□□□□□□

■□□■□□□□□　　

□□■■■□□■□

□□□■□□■■■

□□□□□　　　□□□□□

□□□■□　=>　□□■■□

□□■■■　　　□■□□■

□□□■□　　　□□■■□

要SEARCH的是应该是第一列吧，不是第一行，第一行N

先枚举第一行的情况。。。。

再递推出其它行的情况。。。。

最后检查是否合法。。。。。

。

。

。

再后来就AC了

龘十龘龘十十龘十龘十十龘龘十龘

十龘龘龘十十十龘十十十龘龘龘十

龘龘龘十十龘龘十龘龘十十龘龘龘

龘龘十龘十龘龘十龘龘十龘十龘龘

十十十十龘十十龘十十龘十十十十

十十龘龘十龘龘十龘龘十龘龘十十

龘十龘龘十龘龘十龘龘十龘龘十龘

十龘十十龘十十龘十十龘十十龘十

龘十龘龘十龘龘十龘龘十龘龘十龘

十十龘龘十龘龘十龘龘十龘龘十十

十十十十龘十十龘十十龘十十十十

龘龘十龘十龘龘十龘龘十龘十龘龘

龘龘龘十十龘龘十龘龘十十龘龘龘

十龘龘龘十十十龘十十十龘龘龘十

龘十龘龘十十龘十龘十十龘龘十龘

通过 　　100人

通过人数终于被我刷成十全十美了，

这数据真奇怪，要开到100才过。。害我还用小号掉RP。。

终于做出来了！！！AC！

纪念一下，花了1个小时……

关键要枚举第一行！！一切都迎刃而解。

大家数组一定要开大,至少只开[0..16,0..16]会出现以下情况:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：运行时错误...|错误号: -1073741571

├ 测试数据 10：运行时错误...|错误号: -1073741571

....

这题不会的可以参照"费解的开关"一题

直观的想法是枚举每一个操作,但时间复杂度太高

对于每一次操作,都会改变上一行,本行与下一行的状态,那么对于每一行,除了自身能修改状态之外,只能被上一行与下一行修改,而第一行没有上一行,那么当此行操作已确定时,就只能被第二行修改了,而当第二行的操作已确定时,由于它的上一行即第一行的操作也已确定,所以只能被第三行修改.....依次类推

因此,只要第一行的操作确定,则全部操作都已确定,所以枚举第一行的操作即可,

最多共有15列,每个位置可以选择操作/不操作,则第一行共有2^15=32768个状态,

每次枚举完毕进行检查,有至多100行,每次操作共修改5个格子,所以算法时间复杂度为O(n*2^m)

而对于输出顺序，只要将第一行所进行操作的地方看做１，不进行操作的地方看作０，按顺序枚举即可（实际上是二进制转成十进制再排序）

1

■□■■□□■□■□□■■□■

□■■■□□□■□□□■■■□

■■■□□■■□■■□□■■■

■■□■□■■□■■□■□■■

□□□□■□□■□□■□□□□

□□■■□■■□■■□■■□□

■□■■□■■□■■□■■□■

□■□□■□□■□□■□□■□

■□■■□■■□■■□■■□■

□□■■□■■□■■□■■□□

□□□□■□□■□□■□□□□

■■□■□■■□■■□■□■■

■■■□□■■□■■□□■■■

□■■■□□□■□□□■■■□

■□■■□□■□■□□■■□■

1

经测试，垃圾dfs爆炸了.....无任何剪枝

这是我的失误，不好意思。

我第二次递交题目是正确的，1

输入格式 Input Format

只有一行：n m

(1