题目分析

本题要求在一个网格中找出最大的矩形区域，该区域内所有格子均为'.'。通过枚举所有可能的左右边界，计算每一行在该边界内连续'.'的长度，再利用单调栈或动态规划的思想求解最大矩形面积。

代码实现

#include <bits/stdc++.h>
using namespace std;

int s[210][210];  // 前缀和数组，记录每行从左到右连续'.'的数量
char S[210][210]; // 存储网格信息

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(s, 0, sizeof(s)); // 初始化前缀和数组

    // 读取网格并计算每行的前缀和
    for (int i = 1; i <= n; i++) {
        scanf("%s", S[i] + 1); // 从1开始存储，方便计算
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i][j - 1] + (S[i][j] == '.');
        }
    }

    int ans = 0; // 存储最大矩形面积

    // 枚举所有可能的左右边界x和y
    for (int x = 1; x <= m; x++) {
        for (int y = x; y <= m; y++) {
            int i1 = 0, i2 = 0; // i1和i2记录连续符合条件的行数
            for (int i = 1; i <= n; i++) {
                // 若当前行的x或y列不是'.'，则连续行数重置
                if (S[i][x] != '.' || S[i][y] != '.') {
                    i1 = 0;
                } else {
                    // 检查x到y列是否全为'.'（通过前缀和判断）
                    if (s[i][y] - s[i][x - 1] == y - x + 1) {
                        if (i1 == 0) {
                            i1 = i; // 首次找到连续行，记录起始行
                        } else {
                            i2 = i; // 更新结束行，计算高度
                            ans = max(ans, (y - x + 1) * (i2 - i1 + 1)); // 更新面积
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

算法说明

1. 前缀和预处理：通过计算每行的前缀和数组，快速判断任意区间内是否全为'.'。
2. 枚举边界：固定左右边界x和y，遍历所有可能的列范围。
3. 连续行判断：对每一行，若x到y列全为'.'，则记录连续行数，当连续行数达到2行时，计算矩形面积（宽度为y-x+1，高度为连续行数），并更新最大面积。

该方法时间复杂度为O(n*m²)，适用于n和m较小的网格场景（本题n,m≤200）。