# 遞迴_最大正方形

user_3763047219
c_cpp
a year ago
1.6 kB
3
Indexable
Never
```void findMaximalSquare(int** matrix, int rows, int cols, int* maxEdge);

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) {
int square[15][15];
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <= cols; j++) {
square[i][j] = matrix[i][j];
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i][j] == 1) {
int a = square[i - 1][j - 1];
int b = square[i - 1][j];
int c = square[i][j - 1];
square[i][j] = min(a, b, c) + 1;
if (*maxEdge < square[i][j]) {
*maxEdge = square[i][j];
}
}
}
}

}

#include <stdio.h>
#include <stdlib.h>

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);

}```