Tổng của kính giờ tối đa trong ma trận trong C ++

Trong bài toán này, chúng ta được đưa ra một ma trận. Nhiệm vụ của chúng tôi là tạo một chương trình tìm tổng lớn nhất của đồng hồ cát trong một ma trận bằng C ++.

Mô tả chương trình - Tại đây, chúng tôi sẽ tìm tổng số tối đa của tất cả các đồng hồ có thể được tạo cho các phần tử ma trận đã cho.

Kính giờ là một hình dạng gồm 7 phần tử được tạo trong ma trận ở dạng sau,

X X X
  X
X X X

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

array ={
   {2 4 0 0}
   {0 1 1 0}
   {4 2 1 0}
   {0 3 0 1}}

Đầu ra -

Giải thích -

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

Vì vậy, có thể tạo đồng hồ cát bằng các chỉ số sau,

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]

Chúng ta sẽ tìm tổng của tất cả các phần tử này của mảng từ [0] [0] đến [R2] [C-2] điểm bắt đầu. Và tìm maxSum cho tất cả những chiếc đồng hồ này được tạo từ các phần tử mảng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

Maximum sum of hour glass created is 14