資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學矩陣中沙漏的最大和 C++
在本問題中，我們給定一個矩陣。我們的任務是建立一個程式，找到 C++ 中矩陣中沙漏的最大和。
程式說明 − 在這裡，我們將找到可以為給定矩陣元素建立的所有沙漏的最大和。
沙漏是以以下形式在矩陣中製作的 7 個元素形狀，
X X X X X X X
我們舉一個例子來理解這個問題，
輸入 −
array ={
{2 4 0 0}
{0 1 1 0}
{4 2 1 0}
{0 3 0 1}}輸出 −
解釋 −
Hour glass are : 2 4 0 0 1 1 1 2 4 2 1 0 3 0 4 0 0 1 1 0 1 1 2 1 0 3 0 1
因此，可以用以下索引建立沙漏，
matrix[i][j] matrix[i][j+1] matrix[i][j+2] matrix[i+1][j+1] matrix[i+2][j] matrix[i+2][j+1] matrix[i+2][j+2]
我們將找到從 [0][0] 到 [R2][C-2] 起點的陣列的所有這些元素的和。找到由陣列元素建立的所有這些沙漏的最大和。
示例
程式說明我們解決方案的工作原理，
#include<iostream>
using namespace std;
const int row = 4;
const int col = 4;
int findHourGlassSum(int mat[row][col]){
if (row<3 || col<3)
return -1;
int maxSum = 0;
for (int i=0; i<row-2; i++){
for (int j=0; j<col-2; j++){
int hrSum = (mat[i][j]+mat[i][j+1]+mat[i][j+2])+ (mat[i+1][j+1])+ (mat[i+2][j]+mat[i+2][j+1]+mat[i+2][j+2]);
maxSum = max(maxSum, hrSum);
}
}
return maxSum;
}
int main() {
int mat[row][col] = {
{2, 4, 0, 0},
{0, 1, 1, 0},
{4, 2, 1, 0},
{0, 3, 0, 1}};
int maxSum = findHourGlassSum(mat);
if (maxSum == -1)
cout<<"Not possible";
else
cout<<"Maximum sum of hour glass created is "<<maxSum;
return 0;
}輸出
Maximum sum of hour glass created is 14
更新於： 03-Jun-2020
434 次瀏覽
廣告