洛谷P3135 Fort Moo P

url: https://www.luogu.com.cn/problem/P3135

tag:
枚举，构造，动态规划

思路：
看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。

代码：

#include <iostream>
using namespace std;
const int N = 220;
int n, m;
int d[N][N], s[N][N], col[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.') d[i][j] ++;
            s[i][j] = s[i][j - 1] + d[i][j];
            col[i][j] = col[i - 1][j] + d[i][j];
        }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        {
            for (int k = 1; k <= m; k ++)
            {
                for (int l = k; l <= m; l ++)
                {
                    if (
                            col[j][k] - col[i - 1][k] == j - i + 1
                            && col[j][l] - col[i - 1][l] == j - i + 1
                            && s[i][l] - s[i][k - 1]  == l - k + 1
                            && s[j][l] - s[j][k - 1] == l - k + 1)
                        res = max(res, (j - i + 1) * (l - k + 1));
                }
            }
        }
    cout << res << endl;
    return 0;
}