C++で行列内の砂時計（アワーグラス）の最大合計を求めるプログラム

問題概要

この問題では、1つの行列が与えられます。私たちのタスクは、C++を使って、行列内に存在するすべての「砂時計（アワーグラス）」形状の要素の合計を計算し、その中で最大となる値を見つけるプログラムを作成することです。

プログラムの説明 − 与えられた行列の要素から作成できるすべての砂時計について合計を求め、その最大値（maxSum）を出力します。

砂時計（アワーグラス）とは

砂時計とは、行列の中で次のような形に配置された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}}

出力 − 最大合計は 14

説明 − この行列から作成できる砂時計は以下の通りです。

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]

つまり、3×3 の範囲から四隅と中央の5か所を除いた、上下の行3つずつと中央の1要素を足したものが砂時計の合計になります。

アルゴリズムの考え方

開始位置 [0][0] から [R-2][C-2] までの各座標を起点として、そこから作れる砂時計の7要素の合計をすべて計算します。そして、計算した合計の中で最も大きい値を maxSum として返します。

手順をまとめると以下のようになります。

• 行列のサイズが3未満の場合は砂時計が作れないため、-1 を返す。
• 二重ループで可能なすべての開始位置（i, j）を走査する。
• 各位置で7要素の合計 hrSum を計算する。
• max(maxSum, hrSum) で最大値を更新していく。
• ループ終了後の 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

このように、計算量は O(R×C) となり、行列のサイズに対して線形時間で効率的に最大の砂時計合計を求めることができます。