题目重述

我们有一个 $n \times m$ 的监控面板，每个格子显示"1"（甲楼）或"2"（乙楼）。可以通过四个按钮进行循环移位操作：

• 上：第一行移到最后，其他行上移
• 下：最后一行移到第一，其他行下移
• 左：第一列移到最右，其他列左移
• 右：最后一列移到最左，其他列右移

目标：通过任意次数的操作，使得面板中所有四个格子都相同的 $2 \times 2$ 子矩形数量最大化。

问题分析

1. 操作的本质

循环移位操作具有以下性质：

• 操作是可逆的，且操作顺序可交换
• 任意操作组合等价于将原矩阵进行行循环移位和列循环移位
• 最终效果相当于从原矩阵中选取一个起始位置 $(r, c)$，然后以该位置为左上角取 $n \times m$ 的循环窗口

2. 关键观察

设原矩阵为 $A$，经过操作后的矩阵为 $B$，则：

$$B[i][j] = A[(i + r - 2) \bmod n + 1][(j + c - 2) \bmod m + 1] $$

其中 $r \in [1, n]$ 是行偏移，$c \in [1, m]$ 是列偏移。

算法详解

1. 矩阵扩展策略

为了枚举所有可能的循环移位，我们将原矩阵扩展为 $2n \times 2m$：

for (int i = 1; i <= n; ++i) {
    scanf("%s", s[i] + 1);
    for (int j = 1; j <= m; ++j) {
        s[i][m + j] = s[i][j];  // 列方向复制
    }
    for (int j = 1; j <= m << 1; ++j) {
        s[n + i][j] = s[i][j];  // 行方向复制
    }
}

这样，扩展矩阵中包含了所有可能的 $n \times m$ 循环窗口。

2. 有效性标记

对于扩展矩阵中的每个可能成为 $2 \times 2$ 子矩形左上角的位置 $(i, j)$，检查其有效性：

c[i][j] = s[i][j] == s[i][j + 1] 
        && s[i][j] == s[i + 1][j] 
        && s[i + 1][j] == s[i + 1][j + 1];

条件解释：

• s[i][j] == s[i][j + 1]：第一行两个格子相同
• s[i][j] == s[i + 1][j]：第一列两个格子相同
• s[i + 1][j] == s[i + 1][j + 1]：第二行两个格子相同

由传递性可知，这四个格子都相同。

3. 二维前缀和

构建前缀和数组以便快速计算任意矩形区域内有效 $2 \times 2$ 子矩形的数量：

c[i][j] += c[i][j - 1] + c[i - 1][j] - c[i - 1][j - 1];

前缀和公式：

$$c[i][j] = \text{原值} + c[i][j-1] + c[i-1][j] - c[i-1][j-1] $$

4. 滑动窗口枚举

在扩展矩阵中枚举所有可能的 $n \times m$ 窗口：

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        ans = max(ans, calc(i, j, i + n - 2, j + m - 2));

计算窗口内有效 $2 \times 2$ 子矩形数量的函数：

inline int calc(int a, int b, int x, int y) {
    return c[x][y] - c[a - 1][y] - c[x][b - 1] + c[a - 1][b - 1];
}

注意：窗口边界是 $[i, i+n-2] \times [j, j+m-2]$，因为：

• 一个 $n \times m$ 的矩阵包含 $(n-1) \times (m-1)$ 个可能的 $2 \times 2$ 子矩形
• 每个有效位置对应一个 $2 \times 2$ 子矩形的左上角

算法正确性证明

完备性

扩展矩阵包含了所有 $n \times m$ 的循环移位结果，因此我们枚举了所有可能的最终状态。

无重复计数

每个 $2 \times 2$ 子矩形只被其左上角位置标记一次，不会重复计数。

边界处理

由于我们只检查 $[1, 2n-1] \times [1, 2m-1]$ 范围内的位置作为 $2 \times 2$ 子矩形的左上角，避免了数组越界。

复杂度分析

• 空间复杂度：$O(nm)$，存储扩展矩阵和前缀和数组
• 时间复杂度：
  • 矩阵扩展：$O(nm)$
  • 有效性标记：$O(nm)$
  • 前缀和计算：$O(nm)$
  • 窗口枚举：$O(nm)$
  • 总复杂度：$O(nm)$，完全适用于 $n, m \leq 1000$ 的数据范围

总结与拓展

核心思想

本题的解法体现了几个重要的算法设计思想：

1. 问题转化：将循环移位问题转化为在扩展矩阵中寻找最优窗口
2. 预处理优化：通过前缀和将区间查询优化到 $O(1)$
3. 完备枚举：利用矩阵扩展确保枚举所有可能情况