Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm khu vực ma trận con tối đa có số đếm 1 nhiều hơn số 0.
Đối với điều này, chúng tôi sẽ được cung cấp một ma trận chứa 0 và 1. Nhiệm vụ của chúng ta là lấy ma trận con có diện tích tối đa chứa nhiều hơn 1 chữ 0
Ví dụ
#include <bits/stdc++.h> using namespace std; #define SIZE 10 //finding length of longest sub-matrix int lenOfLongSubarr(int arr[], int n, int& start, int& finish) { unordered_map<int, int> um; int sum = 0, maxLen = 0; for (int i = 0; i < n; i++) { sum += arr[i]; if (sum == 1) { start = 0; finish = i; maxLen = i + 1; } else if (um.find(sum) == um.end()) um[sum] = i; if (um.find(sum - 1) != um.end()) { if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1; finish = i; maxLen = i - um[sum - 1]; } } return maxLen; } //finding the maximum area void largestSubmatrix(int mat[SIZE][SIZE], int n) { int finalLeft, finalRight, finalTop, finalBottom; int temp[n], maxArea = 0, len, start, finish; for (int left = 0; left < n; left++) { memset(temp, 0, sizeof(temp)); for (int right = left; right < n; right++) { for (int i = 0; i < n; ++i) temp[i] += mat[i][right] == 0 ? -1 : 1; len = lenOfLongSubarr(temp, n, start, finish); if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) { finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish; maxArea = (finish - start + 1) * (right - left + 1); } } } cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n"; cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n"; cout << "Maximum area: " << maxArea; } int main() { int mat[SIZE][SIZE] = { { 1, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 1 } }; int n = 4; largestSubmatrix(mat, n); return 0; }
Đầu ra
(Top, Left): (1, 1) (Bottom, Right): (3, 3) Maximum area: 9