221. Maximal Square

递推关系为 len[i][j] = min(min(len[i-1][j], len[i][j-1]), len[i-1][j-1]) + 1;

以(i,j)为右下角的最大方块边长，取决于周围三个位置(i-1,j),(i,j-1),(i-1,j-1)，恰好为三者最小边长扩展1位。

若三者最小边长为0，那么(i,j)自成边长为1的方块。

#define MIN(i, j) (i < j ? i : j)

int maximalSquare(char** matrix, int matrixRowSize, int matrixColSize) {
    if (matrixRowSize == 0) return 0;
    int **dp = (int**)malloc(sizeof(int*) * matrixRowSize);
    int max = 0;
    for (int i = 0; i < matrixRowSize; i++) dp[i] = (int*)malloc(sizeof(int) * matrixColSize);
    for (int i = 0; i < matrixRowSize; i++) {
        dp[i][0] = (matrix[i][0] & 1);
        //if (ans < dp[i][0]) ans = dp[i][0];
        if(matrix[i][0] &1)
            max = 1;
    }
    for (int i = 0; i < matrixColSize; i++) {
        dp[0][i] = (matrix[0][i] & 1);
        if(matrix[0][i] &1)
            max = 1;
    }
    for (int i = 1; i < matrixRowSize; i++) {
        for (int j = 1; j < matrixColSize; j++) {
            if (matrix[i][j] & 1) dp[i][j] = MIN(dp[i - 1][j - 1], MIN(dp[i - 1][j], dp[i][j - 1])) + 1;
            else dp[i][j] = 0;
            if (max < dp[i][j]) max = dp[i][j];
        }
        free(dp[i - 1]);
    }
    free(dp[matrixRowSize - 1]);
    free(dp);
    return max * max;
}