E. Mirror Grid - 题解

比赛与标签

比赛: Codeforces Round 806 (Div. 4) 标签: implementation, *1200 难度: *1200

喵喵的题目解读

哈喵~ 主人 sama，下午好呀！这道题是说呀，我们有一个 n x n 的棋盘，上面摆满了 '0' 和 '1' 的说。

我们的任务是，用最少的操作次数（把 '0' 变成 '1' 或者 '1' 变成 '0'），让这个棋盘变得超级对称！

什么样的对称才算合格呢？就是把它顺时针旋转 0°、90°、180°、270°，看起来都得是一模一样的才行哦！就像下面这张图展示的一样呐。

最后，告诉我们最少需要翻转几次就好啦，喵~

旋转的魔法喵~

主人请想一想，如果一个棋盘旋转之后要和原来一样，那意味着什么呢？

这意味着，对于棋盘上的任何一个格子 (i, j)，它旋转 90°、180°、270° 之后到达的新位置，这几个格子最终必须是同一个数字！它们就像一个“命运共同体”一样，要变都得一起变，喵~

让我们来推导一下旋转的魔法公式吧！对于一个在 (i, j) 的小方块：

• 旋转 0°: 还是它自己 (i, j)
• 旋转 90°: 会跑到 (j, n-1-i)
• 旋转 180°: 会跑到 (n-1-i, n-1-j)
• 旋转 270°: 会跑到 (n-1-j, i)

这四个位置就形成了一个“命运共同体”的小团体！(有时候因为对称，这个小团体可能只有 1 个或 2 个成员哦，比如最中心的格子)。

为了让整个棋盘满足旋转不变性，我们必须让每个“命运共同体”里的所有格子都变成同一个数。要么全变成 '0'，要么全变成 '1'。

那怎么才能最省力气呢？当然是看这个小团体里，是 '0' 多还是 '1' 多啦！

• 如果 '1' 比较少，我们就把所有的 '1' 都翻成 '0'。
• 反之，如果 '0' 比较少，就把 '0' 都翻成 '1'。

这样翻转的次数就是最少的，对吧？也就是 min('0'的数量, '1'的数量) 喵~

所以我们的策略就是：

1. 遍历整个棋盘上的每个格子。
2. 如果一个格子还没被我们处理过，就把它和它旋转后的三个小伙伴们找出来，组成一个“旋转组”。
3. 数一数这个组里有几个 '1' 和几个 '0'。
4. 取 '1' 的数量和 '0' 的数量中较小的一个，累加到我们的总操作次数里。
5. 为了不重复计算，我们可以用一个 visited 数组来标记已经处理过的格子，是不是很聪明呀？喵~

让代码动起来喵！

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<string> grid(n);
        for (int i = 0; i < n; i++) {
            cin >> grid[i];
        }

        // 这个是我们的'记忆'小本本，用来记录哪些格子已经被分过组了，避免重复计算的说。
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        int total_ops = 0;

        // 遍历棋盘上的每一个格子
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 如果发现一个还没被访问过的小格子...
                if (!visited[i][j]) {
                    // 用一个 `set` 来装这个格子和它旋转后的小伙伴们。
                    // `set` 会自动处理重复的坐标，超级方便！
                    set<pair<int, int>> points;

                    // 这里就是计算四个旋转位置的坐标，把它们都加进小团体里。
                    points.insert({i, j});                 // 0 度
                    points.insert({j, n - 1 - i});         // 90 度
                    points.insert({n - 1 - i, n - 1 - j}); // 180 度
                    points.insert({n - 1 - j, i});         // 270 度

                    int count_ones = 0;
                    // 遍历这个小团体里的所有成员
                    for (auto p : points) {
                        int x = p.first;
                        int y = p.second;
                        // 把小团体里的每个成员都标记为'已访问'，以后就不会再管它们啦
                        visited[x][y] = true;
                        // 数一数这个小团体里有多少个 '1'
                        if (grid[x][y] == '1') {
                            count_ones++;
                        }
                    }

                    // 小团体里的成员总数
                    int total_in_set = points.size();
                    // '0' 的数量就是总数减去 '1' 的数量
                    // 计算这个小团体的最小翻转次数，然后加到总数里去。
                    total_ops += min(count_ones, total_in_set - count_ones);
                }
            }
        }

        cout << total_ops << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(n²) 的说。我们基本上把每个格子都访问了一遍。对于每个格子，我们计算它所在小团体的四个位置，这是一个常数时间的操作。因为 visited 数组的存在，每个格子只会被归入一个团体并处理一次，所以总的时间复杂度就是 O(n*n) 的说，非常高效！
• 空间复杂度: O(n²) 的说。我们需要一个 visited 数组来记录格子的访问状态，它的大小和棋盘一样大，所以空间复杂度是 O(n*n) 呐。

喵喵的小课堂

这道题真的很有趣，对吧！让本猫娘来总结一下我们可以学到的小知识点吧：

1. 核心思想: 这道题最核心的思想是 “分组处理”。我们通过分析旋转对称的性质，把整个棋盘上的格子分成了若干个互不相干的“旋转组”。对每个组独立地求最优解，最后加起来就是全局最优解。这是一种很常见的降维打击思路哦！

2. 坐标变换: 学会计算一个点绕中心旋转90度的坐标变换 (i, j) -> (j, n-1-i) 是解决这类网格旋转问题的关键钥匙，一定要记住这个公式喵！

3. 善用数据结构: 代码里巧妙地使用了 std::set 来存储一个组里的坐标。set 既能去重（当n为奇数时，中心点旋转后还是自己），又能方便地遍历，是处理这类问题的好帮手呢。

4. 避免重复: 使用 visited 数组或者只遍历左上角四分之一的区域，是确保每个“旋转组”只被计算一次的关键技巧，可以有效避免重复劳动，保持算法的正确性和效率。

只要掌握了这些，下次再遇到类似的网格旋转问题，主人 sama 一定能轻松解决的！加油喵~！