C++のバイナリ行列ですべてのものによって形成される最大の「+」のサイズを見つけます

この問題では、NxNバイナリ行列bin[][]が与えられます。私たちのタスクは、バイナリ行列内のすべてのものによって形成される最大の「+」のサイズを見つけることです。

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

入力

0 1 1
1 1 1
0 1 0

出力

5

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

この問題の簡単な解決策は、与えられた1の4つの方向すべてで同じである必要がある行列内の点について、一方向に最大数の1を見つける必要がある最大の「+」を見つけることです。ポイントの各辺に1つの行列、つまり4を作成します。各行列には、指定された要素の連続する1の数が格納されます。すべてのインデックス値について、4方向すべての連続するすべての値の最小値である最大値が見つかります。

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

例

#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
   int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
   for (int i = 0; i < N; i++) {
      conOneTop[0][i] = mat[0][i];
      conOneBottom[N - 1][i] = mat[N - 1][i];
      conOneLeft[i][0] = mat[i][0];
      conOneRight[i][N - 1] = mat[i][N - 1];
   }
   for (int i = 0; i < N; i++) {
      for (int j = 1; j < N; j++) {
         if (mat[i][j] == 1)
            conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
         else
            conOneLeft[i][j] = 0;
         if (mat[j][i] == 1)
            conOneTop[j][i] = conOneTop[j - 1][i] + 1;
         else
            conOneTop[j][i] = 0;
         j = N - 1 - j;
         if (mat[j][i] == 1)
            conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
         else
            conOneBottom[j][i] = 0;
         if (mat[i][j] == 1)
            conOneRight[i][j] = conOneRight[i][j + 1] + 1;
         else
            conOneRight[i][j] = 0;
         j = N - 1 - j;
      }
   }
   int maxConOne = 0;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++){
         int ConOnes = min(min(conOneTop[i][j],
         conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
         if(ConOnes > maxConOne)
            maxConOne = ConOnes;
      }
   }
   if (maxConOne)
      return (4 * (maxConOne - 1) + 1);
   return 0;
}
int main() {
   int mat[N][N] = {
      { 1, 0, 1, 1, 1, 1, 0 },
      { 1, 0, 1, 0, 1, 1, 1 },
      { 1, 1, 1, 0, 1, 1, 0 },
      { 0, 0, 0, 0, 1, 0, 0 },
      { 1, 0, 1, 1, 1, 1, 1 },
      { 1, 1, 1, 0, 1, 1, 1 },
      { 1, 0, 0, 0, 1, 0, 0 },
   };
   cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
   return 0;
}

出力

The size of the largest plus formed by ones is 9