Trong bài toán này, chúng ta được đưa ra một bin ma trận nhị phân [] [] có kích thước nXm. Nhiệm vụ của chúng tôi là giải quyết tất cả các truy vấn q. Đối với truy vấn (x, y), chúng ta cần tìm số lượng ma trận con có kích thước x * x sao cho tất cả các phần tử của mảng y (số nhị phân).
Mô tả sự cố
Ở đây, chúng ta cần đếm tổng số ma trận con có kích thước nhất định mà chỉ chứa một trong hai bit, tức là ma trận con sẽ là tất cả các phần tử 0/1.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1) Đầu ra
2
Giải thích
Tất cả ma trận con cỡ 2 với tất cả phần tử 1 là -
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}} Giải pháp cho vấn đề này là sử dụng Lập trình động cách tiếp cận. Để giải quyết, chúng ta sẽ duy trì DP ma trận 2D [] [] để lưu trữ ma trận con lớn nhất của cùng một bit. tức là DP [i] [j] sẽ lưu trữ giá trị của ma trận con có chỉ số cuối là (i, j) và tất cả các phần tử đều giống nhau.
Để bạn hiểu, nếu DP [4] [5] =2, các phần tử tại bin [3] [4], bin [3] [5], bin [4] [4] và bin [4] [5] là giống nhau .
Vì vậy, để tìm DP [i] [j], chúng ta có hai trường hợp -
Trường hợp 1 - nếu i =0 hoặcj =0:DP [i] [j] =1, vì chỉ có thể có một ma trận con.
Trường hợp 2 - nếu không, bin [i- (k-1)] [j] =bin [i] [j - (k-1)]…:trong casae này DP [i] [j] =min (DP [i] [ j-1], DP [i -1] [j], DP [i-1] [j-1]) + 1. Điều này sẽ đóng góp vào ma trận con như, chúng tôi yêu cầu. Hãy tổng quát hóa, trường hợp với k =2, tức là nếu chúng ta xem xét một ma trận con có kích thước 2X2. Sau đó, chúng ta cần kiểm tra xem bin [i] [j] =bin [i] [j - 1] =bin [i- 1] [j] =bin [i -1] [j -1], nếu có thể sau đó, chúng ta sẽ tìm DP [i] [j] cho k =2.
Nếu trường hợp 2 điều kiện không được đáp ứng, chúng tôi sẽ đặt DP [i] [j] =1, có thể được coi là giá trị mặc định.
Giá trị này của DP [i] [j] có thể dành cho một bit đặt hoặc bit không đặt. Chúng ta sẽ kiểm tra giá trị của bin [i] [j] để xem giá trị k thuộc tập hợp hoặc chưa đặt nào. Để tìm tần số, chúng ta sẽ tạo hai mảng, zeroFrequrency để lưu trữ tần suất của ma trận con được tạo ra cho 0. Và mộtFrequrency để lưu trữ tần suất của ma trận con được tạo ra cho 1.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
#define N 3
#define M 4
int min(int a, int b, int c) {
if (a <= b && a <= c)
return a;
else if (b <= a && b <= c)
return b;
else
return c;
}
int solveQuery(int n, int m, int bin[N][M], int x, int y){
int DP[n][m], max = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0)
DP[i][j] = 1;
else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
if (max < DP[i][j])
max = DP[i][j];
}
else
DP[i][j] = 1;
}
}
int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (bin[i][j] == 0)
zeroFrequency[DP[i][j]]++;
else
oneFrequency[DP[i][j]]++;
}
}
for (int i = max - 1; i >= 0; i--) {
zeroFrequency[i] += zeroFrequency[i + 1];
oneFrequency[i] += oneFrequency[i + 1];
}
if (y == 0)
return zeroFrequency[x];
else
return oneFrequency[x];
}
int main(){
int n = 3, m = 4;
int mat[N][M] =
{{ 1, 1, 0, 1},
{ 1, 1, 1, 0},
{ 0, 1, 1, 1}};
int Q = 2;
int query[Q][2] = {{ 2, 1}, { 1, 0}};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is " <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
}
return 0;
} Đầu ra
For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3