题解 | #奶牛的活动面积# DP

知识点

动态规划

思路

维护每个点的上边的连续的C的个数, 左边的连续的C的个数, 以及以该点为右下角的由C组成的正方形的长度;

上边和左边是很好维护的, 我们考虑如果当前点不是左上两条边的点的话, 那么如果满足当前点上面连续的C的个数和左边的连续的C的个数均大于f[i-1][j-1], 那么f[i][j]就可以在f[i-1][j-1]的基础上+1

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param land char字符型vector<vector<>> 
     * @return int整型
     */
    int maximalSquare(vector<vector<char> >& land) {
        int n = land.size(), m = land[0].size();
        vector<vector<int>> l(n, vector<int>(m, 0));
        vector<vector<int>> up(n, vector<int>(m, 0));
        vector<vector<int>> f(n, vector<int>(m, 0));

        int res = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (land[i][j] == 'E') continue;
                l[i][j] = (j ? l[i][j - 1] : 0) + 1;
                up[i][j] = (i ? up[i - 1][j] : 0) + 1;
                if (i == 0 or j == 0) {
                    f[i][j] = 1;
                }
                else {
                    int len = f[i - 1][j - 1];
                    if (l[i][j] > len and up[i][j] > len) f[i][j] = f[i - 1][j - 1] + 1;
                }
                res = max(res, f[i][j]);
            }
        }
        return res * res;
    }
};