在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。 输入:3 3 0 1 1 0 1 1 0 0 0 输出:4 用C语言书写
时间: 2024-02-09 19:10:39 浏览: 61
已知一个只包含 0 和 1 的二进制数,长度不大于 10 ,将其转换为十进制并输出。
以下是使用动态规划算法实现题目要求的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 计算最大正方形的面积
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
int i, j, max_len = 0;
int **dp = (int **) malloc(sizeof(int *) * matrixSize);
for (i = 0; i < matrixSize; i++) {
dp[i] = (int *) malloc(sizeof(int) * (*matrixColSize));
for (j = 0; j < *matrixColSize; j++) {
dp[i][j] = matrix[i][j] - '0';
if (i > 0 && j > 0 && dp[i][j] == 1) {
dp[i][j] = 1 + (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
}
if (dp[i][j] > max_len) {
max_len = dp[i][j];
}
}
}
for (i = 0; i < matrixSize; i++) {
free(dp[i]);
}
free(dp);
return max_len * max_len;
}
int main() {
int matrixSize, matrixColSize;
scanf("%d %d", &matrixSize, &matrixColSize);
char **matrix = (char **) malloc(sizeof(char *) * matrixSize);
int i, j;
for (i = 0; i < matrixSize; i++) {
matrix[i] = (char *) malloc(sizeof(char) * matrixColSize);
for (j = 0; j < matrixColSize; j++) {
scanf(" %c", &matrix[i][j]);
}
}
int area = maximalSquare(matrix, matrixSize, &matrixColSize);
printf("%d\n", area);
for (i = 0; i < matrixSize; i++) {
free(matrix[i]);
}
free(matrix);
return 0;
}
```
在此代码中,我们使用一个二维数组dp来表示以每个位置为右下角的最大正方形的边长。在初始化时,我们将dp数组的值初始化为矩阵中每个位置的值。在计算dp数组的值时,如果当前位置的值为1,则最大边长为上方、左方和左上方三个位置的最小值加上1,即:
```
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
```
最后,我们遍历dp数组,找到最大的dp值,并返回最大面积。在释放内存时,我们依次释放每行的空间和matrix数组的空间。
阅读全文