数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究包含所有 1 的最大尺寸的正方形子矩阵
当提供了一个二进制矩阵时，我们的任务是找出所有元素都为 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
更新日期：17-6-2020
271 次浏览
广告