資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢二進位制矩陣中由全 1 構成的最大“+”號的大小
在這個問題中，我們給定一個 NxN 的二進位制矩陣 bin[][]。我們的任務是找到由二進位制矩陣中所有 1 構成的最大“+”號的大小。
讓我們舉個例子來理解這個問題，
輸入
0 1 1 1 1 1 0 1 0
輸出
5
解決方案方法
解決這個問題的一個簡單方法是找到最大的“+”號，為此我們需要找到矩陣中某個點在某個方向上 1 的最大數量，對於給定的 1，這在所有四個方向上都需要相同。為此，我們將為點的每個方向（即 4 個方向）建立一個矩陣。每個矩陣將儲存給定元素連續 1 的數量。對於所有索引值，我們將找到最大值，該最大值是所有四個方向上所有連續 1 的最小值。
程式說明我們解決方案的工作原理，
示例
#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
for (int i = 0; i < N; i++) {
conOneTop[0][i] = mat[0][i];
conOneBottom[N - 1][i] = mat[N - 1][i];
conOneLeft[i][0] = mat[i][0];
conOneRight[i][N - 1] = mat[i][N - 1];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
else
conOneLeft[i][j] = 0;
if (mat[j][i] == 1)
conOneTop[j][i] = conOneTop[j - 1][i] + 1;
else
conOneTop[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
else
conOneBottom[j][i] = 0;
if (mat[i][j] == 1)
conOneRight[i][j] = conOneRight[i][j + 1] + 1;
else
conOneRight[i][j] = 0;
j = N - 1 - j;
}
}
int maxConOne = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
int ConOnes = min(min(conOneTop[i][j],
conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
if(ConOnes > maxConOne)
maxConOne = ConOnes;
}
}
if (maxConOne)
return (4 * (maxConOne - 1) + 1);
return 0;
}
int main() {
int mat[N][N] = {
{ 1, 0, 1, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
};
cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
return 0;
}輸出
The size of the largest plus formed by ones is 9
更新於: 2021年3月16日
156 次檢視
廣告