在 C++ 中查找由所有 1 组成的最大“+”的大小

在这个问题中,我们给出了一个 NxN 二进制矩阵 bin[][]。我们的任务是在一个二进制矩阵中找到由所有 1 形成的最大“+”的大小。

让我们举个例子来理解这个问题,

输入

0 1 1

1 1 1

0 1 0

输出结果
5

解决方法

该问题的一个简单解决方案是找到最大的“+”,我们需要为矩阵中的一个点在一个方向上找到最大数量的 1,对于给定的 1,该点在所有四个方向上都必须相同。对于这样,我们将为点的每一侧创建一个矩阵,即 4。每个矩阵将存储给定元素的连续 1 的数量。对于所有索引值,我们将找到最大值,即所有四个方向上所有连续值中的最小值。

程序来说明我们的解决方案的工作,

示例

#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<<"由一个组成的最大加号的大小是 "<<findLargestPlusSize(mat);

   return 0;

}

输出结果
由一个组成的最大加号的大小是 9

以上是 在 C++ 中查找由所有 1 组成的最大“+”的大小 的全部内容, 来源链接: utcz.com/z/352693.html

回到顶部