이진 행렬이 주어졌을 때 우리의 임무는 모든 요소가 1인 정방 행렬을 찾는 것입니다.
이 문제를 위해 우리는 주어진 행렬과 차수가 같은 보조 크기 행렬을 만들 것입니다. 이 크기 행렬은 각 항목에서 Size[i, j]가 모두 1인 정방 행렬의 크기임을 나타내는 데 도움이 됩니다. 그 크기 행렬에서 가장 큰 정사각형 행렬의 크기를 얻기 위한 최대 수를 얻습니다.
입력 및 출력
Input: The binary matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 Output: The largest submatrix with all 1’s.
알고리즘
subMatWithOne(given matrix)
입력 - 메인 매트릭스.
출력 - 가장 큰 것이 모두 1인 정방 행렬을 표시합니다.
Begin define subMat whose order is same as given matrix copy first row and first column of given matrix to subMat for all row i (1 to n), do for all column j (1 to n), do if matrix[i, j] = 1, then subMat[i, j] := 1 + minimum of subMat[i, j-1] and subMat[i-1, j-1] else subMat[i, j] := 0 done done maxSize := subMat[0, 0], iMax := 0 and jMax := 0 for all row i and column j, do if maxSize < subMat[i, j], then maxSize := subMat[i, j] iMax := i, jMax := j done print sub matrix from row = iMax to (iMax - maxSize), and column jMax to (jMax - maxSize) End
예
#include<iostream> #define ROW 6 #define COL 5 using namespace std; int matrix[ROW][COL] = { {0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0} }; int min(int a, int b, int c) { return ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c); } void subMatWithOne() { int subMat[ROW][COL]; int maxSize, iMax, jMax; for(int i = 0; i < ROW; i++) //copy first row of matrix to sub matrix subMat[i][0] = matrix[i][0]; for(int j = 0; j < COL; j++) //copy first column of matrix to sub matrix subMat[0][j] = matrix[0][j]; for(int i = 1; i < ROW; i++) { for(int j = 1; j < COL; j++) { if(matrix[i][j] == 1) //find minimum of left, top and diagonal element + 1 subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1; else subMat[i][j] = 0; //if item is 0, put only 0 } } maxSize = subMat[0][0]; iMax = 0; jMax = 0; for(int i = 0; i < ROW; i++) { //find the order of sub square matrix for(int j = 0; j < COL; j++) { if(maxSize < subMat[i][j]) { maxSize = subMat[i][j]; iMax = i; jMax = j; } } } cout << "Subsquare matrix: "<<endl; for(int i = iMax; i > iMax - maxSize; i--) { //print the submatrix using max size for(int j = jMax; j > jMax - maxSize; j--) { cout << matrix[i][j]<<" "; } cout << endl; } } int main() { subMatWithOne(); }
출력
Subsquare matrix: 1 1 1 1 1 1 1 1 1