C++의 이진 행렬에서 1로 구성된 모양의 둘레 찾기

이 문제에서는 0과 1로만 구성된 nXm 크기의 이진 행렬 bin[][]이 제공됩니다. 우리의 임무는 이진 행렬에서 1로 구성된 도형의 둘레를 찾는 것입니다.

촬영한 둘레는 모든 면에서 그림을 덮을 것입니다. 즉,

1개의 단일 값의 경우 둘레는 4입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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

출력

6

설명

셀 (0,0)과 (1, 0)을 연결하여 변 2와 1의 직사각형을 만듭니다. 둘레는 6입니다.

솔루션 접근 방식

문제에 대한 간단한 해결책은 단순히 하나와 둘레에 대한 기여도를 모두 찾은 다음 값을 찾기 위해 모두 더하는 것입니다.

행렬의 둘레에 대한 1의 기여도는, 1만 둘레에 기여하는 경우 최대 기여도는 4입니다.

최소 기여도는 0이며 모든 면이 1로 둘러싸여 있을 때 1입니다.

따라서 행렬의 각 요소에 대해 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