Trong bài toán này, ta được cho một ma trận. Nhiệm vụ: viết chương trình tìm tổng lớn nhất của hình kính giờ (hourglass) trong ma trận trong C++.
Mô tả – tìm tổng lớn nhất của tất cả các hình kính giờ có thể tạo từ các phần tử ma trận.
Hình kính giờ là hình dạng 7 phần tử trong ma trận như sau:
X X X X X X X
Hãy xem ví dụ:
Input –
array ={ {2 4 0 0} {0 1 1 0} {4 2 1 0} {0 3 0 1}}Output –
Giải thích** –
Các hình kính giờ: 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
Hình kính giờ có thể tạo bằng các chỉ số:
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]
Ta tính tổng các phần tử này từ [0][0] đến [R-2][C-2]. Tìm maxSum cho tất cả hình kính giờ.
Ví dụ
Chương trình minh họa giải pháp:
#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<<"Không thể"; else cout<<"Tổng lớn nhất của hình kính giờ là "<<maxSum; return 0; }Kết quả
Tổng lớn nhất của hình kính giờ là 14