Matrix67 费解的开关

Description

你玩过 “ 拉灯 “ 游戏吗？25 盏灯排成一个 5x5 的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 “1” 表示一盏开着的灯，用数字 “0” 表示关着的灯。下面这种状态

在改变了最左上角的灯的状态后将变成：

再改变它正中间的灯后状态将变成：

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

Input

第一行有一个正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于 30% 的数据，；
对于 100% 的数据，。

Output

输出数据一共有 n 行，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，请输出 “-1”。

Sample Input

Sample Output

1
2
3

3
2
-1

Limit

Time Limit	Memory Limit
C/C++/Rust/Pascal 1 秒，其他语言 2 秒	C/C++/Rust/Pascal 32 M，其他语言 64 M

Analysis

一共有盏灯排成一个的方形。如果将所有行拼接在一起，可以得到一串长度为的字符串，可以由位 int 存储，即盏灯的开关状态可以压缩，至于改变一个灯的状态会产生的连锁反应可以交给一个辅助函数来完成操作。

那么可以建立这样一个模型：盏灯的初始状态作为树的根节点，对于每个状态，可以对其中个位进行操作，即高度为的叉树。递归树的时间复杂度为即，如果按每秒执行次计算的话大概需要 2s，但是也不一定不能在中计算出结果，我们可暂时认为是可以通过的。

但是上述解法只适用于只有一次任务的情况。本题，即最大可能有 500 个任务，使用上述解法显然不能通过本题。

反向思考的话，只需要一次递归树。即从位全的状态递归出高度为的叉树，存储每个树节点，所有输入任务的状态若命中树节点，则表示该状态可以在步内回到灯全亮的状态。树节点的规模为，用 int 存储的话需要的存储空间，即，显然会超出内存限制。

不，我们对上述解法的状态标记数组的规模有误解。状态最大为位全，如果用数组存储，只需要个 int 即的空间即可标记所有状态。即刚才考虑的树节点中会出现重复节点。但是很可惜，还是超过了题目的内存限制。

总之，现在有三个思考方向：

递归树剪枝
优化状态标记数组的空间
思考新的解法

对于「递归树剪枝」，由于树中会出现重复节点，而重复节点状态的子树都是相同的，所以可以剪枝？
考虑这种情况：某状态节点第一次出现的时候没有出度（即叶节点），但是在后续的递归过程中该节点有出现了，但是此时有会有出度（非叶节点），此时若被剪枝，则无法得到所有的过程状态。
但如果有记录每个状态到达过的最浅深度：只有当前到达不比已记录的更浅时才剪枝；若以更浅深度到达，就更新并继续展开。
或者用 BFS，首次到达状态时就是最少步数，不过 BFS 在叶节点时空间占用很大，可能会 heap overflow，就不尝试了。

对于「优化状态标记数组的空间」，应该可以使用布隆过滤器来实现… 但是适合本题的散列算法我设计不出来。
嗯，即对于标记是否出现的节点其实也不必开一个规模为的数组，只需要按位标记即可，用 unsigned int st[((1 << 25) - 1) / 32 + 1]，假设状态 2（即 0000000000000000000000010）访问过，只需将st[2 / 32] |= 1 << (2 % 32) 即可完成标记。而这个状态标记数组只需要的内存。

问题解决了，接下来只需要考虑最后一个问题：某状态的最浅深度怎么存储。
最浅深度直接用 int 存储的话和之前一样需占用内存。不过深度的取值范围为只需要就能表示，即需要空间即可。

哦，空间还能再优化一点：记录最大深度的数组同时可以完成状态标记数组的职责（比如设置位全代表未访问），所以单独的状态标记数组是不必要的。

Solve

综上分析，我们将灯的状态压缩为位数，采用剪枝的 DFS 从位全的状态进行深度最大为的递归，在递归过程中维护一个记录状态对应出现深度最浅的高度的压缩后的数组 path，剪枝的策略是只有当前到达不比已记录的更浅时才剪枝；若以更浅深度到达，就更新并继续展开。

对于时间复杂度，若不考虑剪枝，深度为 0 到 6 的完整递归树共有个节点，因此 DFS 的时间复杂度上界为。最浅深度剪枝只会减少递归调用，不会增加这个上界。该预处理只进行一次；之后每个输入状态只需查询一次 path，查询为。读入每个状态需要处理 25 个字符，因此总时间复杂度为，应该能在内通过，并且我们的剪枝能大幅减少多余的递归~~（我也不知道能降低多少，但是在内通过应该问题不大）~~。

对于空间复杂度，状态总数为，path 中每个状态使用 3 bit 存储，深度 0 到 6 分别编码，编码 7 表示未访问，因此数组共占bit，即 12 MiB。DFS 最大递归深度为 6，递归栈只占空间；若将全部输入状态暂存，还需个状态的空间。因此总空间约为 12 MiB 加少量辅助空间，能够满足题目的内存限制。

#include <iostream>
#include <cstring>
#define x first
#define y second
using PII = std::pair<int, int>;
using uint32_t = unsigned int;

const int D = 6;
const int N = (1 << 25) * 3 / 32 + 10;

uint32_t n, t;
PII dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
uint32_t path[N];

uint32_t op(uint32_t st, uint32_t idx) {
    int i = idx / 5, j = idx % 5;
    st ^= 1u << idx;

    for (uint32_t k = 0; k < 4; ++k) {
        int I = i + dir[k].first;
        int J = j + dir[k].second;
        if (I >= 0 && I < 5 && J >= 0 && J < 5)
            st ^= 1u << (I * 5 + J);
    }
    return st;
}


uint32_t getH(uint32_t st) {
    uint32_t i = st * 3 / 32;
    uint32_t j = st * 3 % 32;
    uint32_t h = 0;

    for (uint32_t k = 0; k < 3; ++k) {
        uint32_t p = j + k;
        uint32_t word = i + p / 32;
        uint32_t bit = p % 32;
        h |= ((path[word] >> bit) & 1u) << k;
    }

    return h;
}


void setH(uint32_t st, uint32_t h) {
    uint32_t oh = getH(st);
    h = std::min(h, oh);

    uint32_t i = st * 3 / 32;
    uint32_t j = st * 3 % 32;

    for (uint32_t k = 0; k < 3; ++k) {
        uint32_t p = j + k;
        uint32_t word = i + p / 32;
        uint32_t bit = p % 32;
        uint32_t mask = 1u << bit;

        path[word] = (path[word] & ~mask) | ((h & 1u) << bit);
        h >>= 1;
    }
}


void dfs(uint32_t st, uint32_t h) {
    if(getH(st) <= h) return ;
    setH(st, h);
    if(h == D) return ;
    
    for(uint32_t i = 0; i < 25; ++i)
        dfs(op(st, i), h + 1);
}

int main () {
    std::cin >> n;
    
    std::memset(path, 0xff, sizeof path);
    
    dfs((1 << 25) - 1, 0);
    
    while(n--) {
        uint32_t st = 0;
        std::string s;
        for (uint32_t i = 0; i < 5; ++i) {
            std::cin >> s;
            for (uint32_t j = 0; j < 5; ++j) {
                if (s[j] == '1')
                    st |= 1u << (i * 5 + j);
            }
        }
        uint32_t h = getH(st);
        if(h <= 6) std::cout << h << '\n';
        else std::cout << "-1\n";
    }
    
    return 0;
}

Ex

我们的解法时间复杂度确实较高。《算法竞赛进阶指南》介绍了一种利用棋盘行结构的解法。

对于这个的 01 矩阵点击游戏，可以观察到以下三个性质：

在最少点击方案中，每个位置至多被点击一次。因为同一位置点击两次会相互抵消，删去这两次点击不会改变最终状态。
固定第一行的点击方案后，后续各行的点击方案至多只有一种。具体来说，当第行已经固定后，如果某一位仍为 1，就必须点击第行同一列的位置，才能将第行该位置变为 0。从上到下递推，即可唯一确定后续各行的点击方案。
点击的先后顺序不影响最终结果。

因此，可以先枚举第一行的点击方案。第一行共有种可能。对于每一种方案，都从第一行开始向下递推：如果第行某一位仍为 1，就点击第行同一列的位置。到达第五行后，如果该行仍有 1，则说明当前方案不合法；否则统计总点击次数，并在所有合法方案中取最小值。

枚举第一行方案时，可以用位运算遍历到这个五位二进制数。若当前数的第位为 1，其中，就点击第一行第列的位置。由于这种枚举涵盖了第一行的所有点击方案，该方法能够覆盖所有可能的解。

代码实现如下：

#include <iostream>
#define x first
#define y second
using uint32_t = unsigned int;
using PII = std::pair<int, int>;

const int N = 5;
const int D = 6;
const PII dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

uint32_t op(uint32_t st, int idx) {
    int i = idx / N;
    int j = idx % N;

    st ^= 1u << idx;

    for (int k = 0; k < 4; ++k) {
        int I = i + dir[k].x;
        int J = j + dir[k].y;
        if (I >= 0 && I < N && J >= 0 && J < N)
            st ^= 1u << (I * N + J);
    }
    return st;
}

int solve(uint32_t init) {
    int ans = D + 1;

    for (uint32_t first = 0; first < (1u << N); ++first) {
        uint32_t st = init;
        int cnt = 0;

        for (int j = 0; j < N; ++j) {
            if ((first >> j) & 1u) {
                st = op(st, j);
                ++cnt;
            }
        }

        bool tooMany = cnt > D;

        for (int i = 1; i < N && !tooMany; ++i) {
            for (int j = 0; j < N; ++j) {
                int idx = (i - 1) * N + j;
                if (((st >> idx) & 1u) == 0) {
                    st = op(st, i * N + j);
                    if (++cnt > D) {
                        tooMany = true;
                        break;
                    }
                }
            }
        }

        if (tooMany) continue;

        uint32_t lastRow = (st >> ((N - 1) * N)) & ((1u << N) - 1);
        if (lastRow == (1u << N) - 1)
            ans = std::min(ans, cnt);
    }

    return ans <= D ? ans : -1;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;

    while (t--) {
        uint32_t st = 0;

        for (int i = 0; i < N; ++i) {
            std::string row;
            std::cin >> row;
            for (int j = 0; j < N; ++j) {
                if (row[j] == '1')
                    st |= 1u << (i * N + j);
            }
        }

        std::cout << solve(st) << '\n';
    }

    return 0;
}

对于时间复杂度，每个棋盘枚举第一行的种点击方案。对于每种方案，至多检查个第一行位置，并向下检查后续行的个位置；每次点击最多改变自身及四个相邻位置，所需时间为。因此，处理一个棋盘的时间复杂度为，处理个棋盘的总时间复杂度为。在本题中，棋盘大小固定为，所以总时间复杂度可简化为。当时，最多约检查个位置。

额外空间方面，程序逐个处理棋盘，只保存当前棋盘状态及少量辅助变量，因此空间复杂度为。

Loading...