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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param land char字符型二维数组
     * @return int整型
     */
    public int maximalSquare (char[][] land) {
        // write code here
        int m = land.length; // 获取地块的行数
        int n = land[0].length; // 获取地块的列数

        int[][] dp = new int[m][n]; // 创建动态规划数组dp，初始化为0
        int maxSide = 0; // 记录最大边长

        // 初始化dp数组的第一行和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = land[i][0] == 'C' ? 1 : 0;
            maxSide = Math.max(maxSide, dp[i][0]);
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = land[0][j] == 'C' ? 1 : 0;
            maxSide = Math.max(maxSide, dp[0][j]);
        }

        // 填充dp数组，使用状态转移方程
        // dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (land[i][j] == 'C') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide; // 返回最大面积，即最大边长的平方
    }
}

编程语言是Java。

该题考察的知识点是动态规划

代码的文字解释如下：初始化dp数组的第一行和第一列。遍历第一行和第一列，如果land[i][j]等于字符'C'，则dp[i][j]赋值为1，表示以当前位置为右下角的正方形的最大边长为1；否则，赋值为0。同时，更新maxSide的值。

利用状态转移方程填充dp数组。对于其他位置(i, j)，如果land[i][j]等于字符'C'，则dp[i][j]的值由其上方、左方和左上方的dp值决定，取其中最小的dp值加1。同时，更新maxSide的值。