이 문제에서는 nXm 크기의 이진 행렬 bin[][]이 제공됩니다. 우리의 임무는 모든 q 쿼리를 해결하는 것입니다. 쿼리(x, y)의 경우 배열 y의 모든 요소(이진수)가 되도록 크기 x*x의 부분행렬의 수를 찾아야 합니다.
문제 설명
여기서 우리는 두 비트 중 하나만으로 구성된 주어진 크기의 부분행렬의 총 수를 계산해야 합니다. 즉, 부분행렬은 모든 요소가 0/1이 됩니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1) 출력
2
설명
모든 요소가 1인 크기 2의 모든 부분행렬은 -
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}} 이 문제에 대한 해결책은 동적 프로그래밍을 사용하는 것입니다. 접근하다. 이를 해결하기 위해 동일한 비트의 가장 큰 부분행렬을 저장하기 위해 2D 행렬 DP[][]를 유지합니다. 즉, DP[i][j]는 끝 인덱스가 (i, j)이고 모든 요소가 동일한 부분 행렬의 값을 저장합니다.
이해를 돕기 위해 DP[4][5] =2이면 bin[3][4], bin[3][5], bin[4][4] 및 bin[4][5]의 요소가 동일합니다. .
따라서 DP[i][j]를 찾기 위해 두 가지 경우가 있습니다. -
사례 1 − if i =0 orj =0 :DP[i][j] =1, 하나의 부분행렬만 가능하므로
사례 2 - 그렇지 않으면, bin[i-(k-1)][j] =bin[i][j - (k-1)] …:이 경우 DP[i][j] =min(DP[i][ j-1] , DP[i -1][j], DP[i-1][j-1] ) + 1. 이것은 우리가 요구하는 것과 같은 부분행렬에 기여할 것입니다. k =2인 경우, 즉 크기가 2X2인 부분행렬을 고려하는 경우를 일반화해 보겠습니다. 그런 다음 가능한 경우 bin[i][j] =bin[i] [j - 1] =bin[i- 1][j] =bin[i -1 ][j -1 ]인지 확인해야 합니다. 그러면 k =2 에 대한 DP[i][j]를 찾을 수 있습니다.
case 2의 조건이 충족되지 않으면 DP[i][j] =1로 설정하며 이는 기본값으로 처리될 수 있습니다.
DP[i][j]의 이 값은 설정 비트 또는 설정되지 않은 비트일 수 있습니다. bin[i][j]의 값을 확인하여 k 값이 설정되거나 설정되지 않은 값 중 어느 것이 속하는지 확인합니다. 주파수를 찾기 위해 0에 대해 생성되는 부분행렬의 주파수를 저장하는 zeroFrequrency와 1에 대해 생성되는 부분행렬의 주파수를 저장하는 oneFrequrency라는 두 개의 배열을 생성합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#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;
} 출력
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