Maximum Sum of Hourglass in Matrix ใน C++

ปัญหา

มีเมทริกซ์ หา Hourglass ที่มีผลรวมสูงสุด Hourglass เป็นรูป 7 เซลล์:

X X X
  X
X X X

ตัวอย่าง

Matrix 4x4:
{2,4,0,0}
{0,1,1,0}
{4,2,1,0}
{0,3,0,1}
Max Hourglass Sum = 14

วิธีแก้

Hourglass เริ่มที่ (i,j) ประกอบด้วย:

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]

วน i=0 ถึง R-3, j=0 ถึง C-3 คำนวณผลรวม หาค่าสูงสุด

ตัวอย่างโค้ด C++

#include<iostream>
using namespace std;

const int row = 4, 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