排兵布阵 题解

题目分析

本题给出一张 $n \times m$ 的网格地图，其中 $1$ 表示可以排兵的格子，$0$ 表示不可排兵。我们需要在里面找出一个内部全是 $1$ 的矩形区域，并求出这个矩形最多包含多少个格子（即矩形的面积）。

数据范围很小：$n,m \le 12$。这意味着即使使用相对暴力的方法，只要控制好循环层数，也是可以在时限内通过的。

解题思路

要找最大的全 $1$ 矩形，最直接的想法就是枚举所有可能的矩形，检查它是否全为 $1$，并更新最大值。

一个矩形由四个量决定：上边界、下边界、左边界、右边界。我们可以枚举这四个边界：

• 先固定上边界 u（从第 1 行到第 n 行）；
• 再固定左边界 l（从第 1 列到第 m 列）；
• 然后固定下边界 d（从第 u 行到第 n 行）；
• 最后从左到右扩展右边界 r（从第 l 列开始）。

在扩展右边界 r 的过程中，我们需要判断新增的这一列（第 r 列）在上下边界 u 到 d 之间是否全部是 $1$。如果出现了 $0$，那么之后更大的 r 也一定包含这个 $0$，因此可以直接停止向右扩展，继续枚举下一个左边界或上下边界。

这样枚举的好处是：在固定上、下、左三个边界之后，我们边扩展右边、边检查合法性，一旦非法就及时退出，避免无意义的循环。同时，在每次右边界合法时，用当前矩形大小 $(r-l+1) \times (d-u+1)$ 更新答案。

算法说明（参考代码）

上面的思路对应的 C++ 代码如下（已给出）：

cpp
复制
1#include <algorithm>
2#include <cstdio>
3using namespace std;
4const int N = 15;
5int n, m;
6int a[N][N];
7int ans;
8int main() {
9    scanf("%d%d", &n, &m);
10    for (int i = 1; i <= n; i++)
11        for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
12
13    for (int u = 1; u <= n; u++)          // 枚举上边界
14        for (int l = 1; l <= m; l++)      // 枚举左边界
15            for (int d = u; d <= n; d++) { // 枚举下边界
16                int chk = 1;              // 检查标记，1 表示当前列合法
17                for (int r = l; r <= m; r++) { // 向右扩展右边界
18                    // 检查第 r 列在 u~d 行范围内是否全是 1
19                    for (int x = u; x <= d; x++) 
20                        chk &= a[x][r];   // 一旦有 0，chk 就会变成 0
21                    if (!chk) break;      // 不合法，停止向右扩展
22                    // 合法，更新答案
23                    ans = max(ans, (r - l + 1) * (d - u + 1));
24                }
25            }
26
27    printf("%d\n", ans);
28    return 0;
29}

代码解释

• a[N][N] 存储地图，下标从 $1$ 开始方便理解。
• 外层两重循环枚举矩形上边界 u 和左边界 l。
• 再内层枚举下边界 d（从 u 到 n），因为矩形的下边界不会小于上边界。
• 变量 chk 初始化为 1。每次向右移动右边界 r 时，检查第 r 列是否完全由 1 组成：遍历行号从 u 到 d，用 chk &= a[x][r] 累积结果。若该列存在 0，chk 变为 0 且之后不会再变回 1。
• 一旦 chk == 0，说明当前及以后更靠右的矩形都会包含 0，直接 break 跳出扩展右边界的内循环。
• 若 chk == 1，计算当前矩形面积 (r - l + 1) * (d - u + 1)，并用 max 更新全局答案 ans。

时间复杂度分析

• 枚举上边界 u：$O(n)$
• 枚举左边界 l：$O(m)$
• 枚举下边界 d：$O(n)$
• 枚举右边界 r 并检查列：检查一列需要遍历 $O(d-u+1) = O(n)$ 行，最多检查 $O(m)$ 列。

因此最坏时间复杂度为 $O(n \times m \times n \times m \times n) = O(n^3 m^2)$。代入最大值 $n=m=12$，计算量约为 $12^5 = 248832$，远小于 $10^8$，可以在 1 秒内轻松通过。

总结

本题由于数据规模很小，直接枚举矩形边界是可行的。关键优化在于固定左边界后，顺次向右扩展右边界并实时检查合法性，一旦遇到非法列就提前结束，避免了不必要的循环。当然，这题也可以使用悬线法或单调栈等更高效的方法（复杂度可降至 $O(nm)$），不过对于 $n,m \le 12$ 的数据来说，上述枚举方法已经足够简单且高效。