ผลรวมสูงสุดของแก้วชั่วโมงในเมทริกซ์ใน 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] และหาค่า maxSum ของนาฬิกาทรายเหล่านี้ที่สร้างขึ้นจากองค์ประกอบอาร์เรย์

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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