C++のバイナリ行列で1で形成された形状の周囲を検索します

この問題では、0と1のみで構成されるサイズnXmのバイナリ行列bin[][]が与えられます。私たちのタスクは、バイナリ行列で1で形成された形状の周囲を見つけることです。

取られた周囲は、すべての側面から図をカバーします。つまり、

1つの単一値の場合、周囲長は4です。

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

入力

bin[][] = [1, 0]
   [1, 0]

出力

6

説明

セル（0,0）と（1、0）は、辺2と1の長方形を作るように接続されています。周囲長は6です。

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

この問題の簡単な解決策は、1つすべてとその境界への寄与を見つけてから、すべてを加算して値を見つけることです。

行列の周囲への1の寄与は、次のとおりです。1だけが周囲に寄与する場合、最大の寄与は4です

1がすべての側面で1に囲まれている場合、最小の寄与は0です。

したがって、行列の各要素について、それが1であるかどうかを確認する必要があります。 all1の場合、隣接するものを見つけて、境界に貢献し、最後に境界を見つけます。

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

例

#include<iostream>
using namespace std;
#define R 3
#define C 5
int contibutionToPerimeter(int mat[][C], int i, int j) {
   int neighbours = 0;
   if (i > 0 && mat[i - 1][j])
      neighbours++;
   if (j > 0 && mat[i][j - 1])
      neighbours++;
   if (i < R-1 && mat[i + 1][j])
      neighbours++;
   if (j < C-1 && mat[i][j + 1])
      neighbours++;
   return (4 - neighbours);
}
int calcPerimeter(int mat[R][C]){
   int perimeter = 0;
   for (int i = 0; i < R; i++)
      for (int j = 0; j < C; j++)
         if (mat[i][j] == 1)
            perimeter += contibutionToPerimeter(mat, i ,j);
   return perimeter;
}
int main() {
   int mat[R][C] = { {0, 1, 0, 0, 0},
   {1, 1, 1, 1, 0},
   {1, 1, 0, 1, 1} };
   cout<<"The perimeter of shapes from formed with 1s is "<<calcPerimeter(mat);
   return 0;
}

出力

The perimeter of shapes from formed with 1s is 18