164. 最大正方形
user_6817964
c_cpp
3 years ago
1.3 kB
6
Indexable
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); }
Editor is loading...