遞迴_最大正方形

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

}