164. 最大正方形

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

}