题解：P3135 [USACO16JAN] Fort Moo P

· · 题解

原题链接

题目大意：

现给定一个 n 行 m 列的字符矩阵 c。请输出能围出的最大竖直摆放的矩形面积，使得矩形的边上没有 \texttt{X}。

思路：

使用前缀和优化暴力的算法可以通过本题，时间复杂度为 \Theta(n^2m^2)。在本题解中，我们将讨论 \Theta(n^2m) 的解法。

我们先枚举矩阵的左上角和右下角的横坐标，不妨设左上角的横坐标为 i，右上角的横坐标为 j。我们预处理出 r_{i,j} 表示第 i 行前 j 列有多少个 \texttt{X}，c_{i,j} 表示第 j 列前 i 行有多少个 \texttt{X}。特别的，r_{i,0}=c_{0,i}=0。显然 k 对于 \forall m\in[i,j]\cap\mathbb{N} 都有 c_{m,k} 不是 \texttt{X} 等价于 c_{j,k}=c_{i-1,k}。所以，我们可以通过枚举一遍 k 来处理出一个长度为 a 数组 p，其中的元素严格从小到大排列且所构成的集合为上述所有 k 所构成的集合。然后，我们用双指针的方法来在线处理出对于每一个纵坐标 k 的最大 l 使得以 (i,k) 为左上角、(j,l) 为右下角的矩形的边框上没有 \texttt{X}。具体详见代码。然后，我们将所有 (j-i+1)(l-k+1) 的最大值算出来输出即可。

上代码：

#include <iostream>
using namespace std;

char mp[201][201];
int pre_row[201][201], pre_column[201][201], column[201];

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);// cin、cout 优化
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> mp[i][j];
        }
    }
    // 预处理前缀和
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            pre_row[i][j] = pre_row[i][j - 1];
            if (mp[i][j] == 'X'){
                pre_row[i][j]++;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            pre_column[i][j] = pre_column[i - 1][j];
            if (mp[i][j] == 'X'){
                pre_column[i][j]++;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        for (int k = i; k <= n; k++){
            // 预处理出所有满足条件的纵坐标
            int sz_column = 0;
            for (int j = 1; j <= m; j++){
                if (pre_column[k][j] == pre_column[i - 1][j]){
                    column[++sz_column] = j;
                }
            }
            int lft = 1, rght = 1;
            while (lft <= sz_column){
                if (mp[i][column[lft]] == 'X' || mp[k][column[lft]] == 'X'){// 如果满足条件的纵坐标已经找完
                    break;
                }
                rght = lft;
                while (rght < sz_column && pre_row[i][column[rght + 1]] == pre_row[i][column[lft] - 1] && pre_row[k][column[rght + 1]] == pre_row[k][column[lft] - 1]){// 判断横向的边框上没有 X
                    rght++;
                }
                ans = max(ans, (k - i + 1) * (column[rght] - column[lft] + 1));
                lft = rght + 1;
                while (lft < sz_column && mp[i][column[lft]] == 'X'){// 继续寻找新的起点
                    lft++;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}