C++のマトリックスで正方形の最大辺の長さを見つける

この問題では、サイズnの2次元行列mat[][]が与えられます。nは奇数です。私たちのタスクは、マトリックス内の正方形の最大辺の長さを見つけることです。

問題の説明 −周囲の値が同じで、行列と同じ中心を共有する正方行列の長さを見つける必要があります。

問題を理解するために例を見てみましょう

入力

mat[][] = {
   {2, 4, 6, 6, 5},
   {1, 7, 7, 7, 3},
   {5, 7, 0, 7, 1},
   {3, 7, 7, 7, 1},
   {2, 0, 1, 3, 2}
}

出力

3

ソリューションアプローチ

この問題の簡単な解決策は、奇数の行列であるため、行列の中心要素を見つけることです。中心要素はインデックス（n / 2、n / 2）にあります。中心を見つけた後、すべての2Dサブを見つけます。その周りの行列は、そのすべての要素が同じであるかどうかをチェックします。

中心から離れたインデックスiの部分行列は、インデックス（n / 2 --1）から（n / 2 + 1）までのrow（n / 2 --1）および（n / 2 + 1）の要素を持ちます。また、インデックス（n / 2 --1）から（n / 2 + 1）までの列（n / 2 --1）および（n / 2 + 1）の要素がその周囲に含まれます。 0からn/2までのiの値の部分行列が、すべての周囲要素が同じであるかどうかを確認する必要があります。

ソリューションの動作を説明するプログラム

例

#include <iostream>
#define n 5
using namespace std;
int findMaxSideSquare(int matrix[][n]) {
   int squareLen = 1;
   for (int i = 0; i < n / 2; i++) {
      int sideVal = matrix[i][i];
      bool isSquare = true;
      for (int j = i; j < n - i; j++) {
         if (matrix[i][j] != sideVal)
            isSquare = false;
         if (matrix[n - i - 1][j] != sideVal)
            isSquare = false;
         if (matrix[j][i] != sideVal)
            isSquare = false;
         if (matrix[j][n - i - 1] != sideVal)
            isSquare = false;
      }
      if (isSquare)
         squareLen = n - 2 * i;
   }
   return squareLen;
}
int main() {
   int mat[n][n] = {
      {2, 4, 6, 6, 5},
      {1, 7, 7, 7, 3},
      {5, 7, 0, 7, 1},
      {3, 7, 7, 7, 1},
      {2, 0, 1, 3, 2}
   };
   cout<<"The maximum side length of square in a Matrix is "<<findMaxSideSquare(mat);
   return 0;
}

出力

The maximum side length of square in a Matrix is 3