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

考察的知识点：动态规划；

解答方法分析：

1. 定义变量m和n，分别表示输入二维数组的行数和列数。
2. 创建一个三维数组dp，dp[i][j][k]表示以第i行第列为右下角的正方形的最大边长，k取值为0、1、2，分表示以该点为右下角的正方形的最大边长计算方式（0代表以水平向延伸，1代表以垂直方向延伸，2代表以对角线方向延伸）。
3. 初始化ans为-1，用于记录最大的正方形边长的平方。
4. 遍历二维数组，外层循环遍历行，内层循环遍历列。
5. 对于每个点，如果为字符’C’，则进行如下操作：更新dp[i][j][0]为dp[i][j-1][0] + 1，表示以当前点为右下角的正方形在水平方向上的最大边长。更新dp[i][j][1]为dp[i-1][j][1] + 1，表示以当前点为右角的正方形在垂直方向上的最大边长。判断是否可以以对角线方向延伸，条件是dp[i][j1] >= dp[i-1][j-1][2] + 1且dp[i][j][0] >= dp[i-1][j-1][2] + 1，如果满足条件，则更新dp[i][j][]为dp[i-1][j-1][2] + 1，表示以当前点为右下角的正方形在对角线方向上的最大边长，否则更新为1。
6. 如果当前点为其他字符，则将dp[i][j][0]、dp[i][j][1]和dp[i][j][2]都设置为0。
7. 在每次内层循环结束后，更新ans为当前正方形边长的平方和ans的较大值。
8. 返回ans的值，即为最大的正方形面积。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param land char字符型vector<vector<>>
     * @return int整型
     */
    int maximalSquare(vector<vector<char> >& land) {
        int m = land.size(), n = land[0].size();
        vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(3,
                                       0)));
        int ans = -1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (land[i - 1][j - 1] == 'C') {
                    dp[i][j][0] = dp[i][j - 1][0] + 1;
                    dp[i][j][1] = dp[i - 1][j][1] + 1;
                    if (dp[i][j][1] >= dp[i - 1][j - 1][2] + 1 &&
                            dp[i][j][0] >= dp[i - 1][j - 1][2] + 1) {
                        dp[i][j][2] = dp[i - 1][j - 1][2] + 1;
                    } else {
                        dp[i][j][2] = 1;
                    }
                } else {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                    dp[i][j][2] = 0;
                }
                ans = max(ans, dp[i][j][2]);
            }
        }
        return ans * ans;
    }
};