# 164. 最大正方形

user_6817964
c_cpp
2 years ago
1.3 kB
2
Indexable
Never
```int min(int a, int b, int c);
int min(int a, int b, int c) {
if (a <= b && a <= c) {
return a;
}
else if (b <= a && b <= c) {
return b;
}
else if (c <= a && c <= b) {
return c;
}
}

void findMaximalSquare(int** matrix, int rows, int cols, int* maxEdge);
void findMaximalSquare(int** matrix, int rows, int cols, int* maxEdge) {
int dp[15][15];

for (int i = 0; i < rows + 1; i++) {
for (int j = 0; j < cols + 1; j++) {
dp[i][j] = matrix[i][j];
}
}

for (int i = 1; i < rows + 1; i++) {
for (int j = 1; j < cols + 1; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;

if (*maxEdge < dp[i][j]) {
*maxEdge = dp[i][j];
}

}
}
}

}

int main() {
int row, col;
scanf("%d %d", &row, &col);
int** matrix = (int**)malloc(row * sizeof(int*));
int i, j, tmp;
for (i = 0; i < row; i++) {
matrix[i] = (int*)malloc(col * sizeof(int));
}
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
scanf("%d", &tmp);
matrix[i][j] = tmp;
}
}

int maxEdge = 0;
findMaximalSquare(matrix, row - 1, col - 1, &maxEdge);

printf("%d", maxEdge * maxEdge);
for (i = 0; i < row; i++) {
free(matrix[i]);
}
free(matrix);

}```