C++에서 이웃 채우기의 최소 반복을 사용하여 배열을 1로 채우기

이 문제에서는 0 또는 1인 n개의 요소로 구성된 배열 arr이 제공됩니다. 우리의 임무는 이웃 채우기의 최소 반복을 사용하여 배열을 1로 채우는 것입니다.

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

입력: arr[] ={0, 1, 1, 0, 0, 1}

출력: 1

해결 방법 -

문제를 해결하려면 위치에 1이 있으면 인접한 두 개의 0을 1로 변환할 수 있다는 사실을 알아야 합니다.

만약, arr[i]는 1이다.
그러면 arr[i-1]과 arr[i+1]이 1로 변환됩니다.

이를 사용하여 다음 경우 중 하나를 사용하여 솔루션을 찾을 수 있습니다.

사례 1: 블록은 블록의 시작과 끝이 1입니다. 나머지 값은 모두 0입니다. 0의 개수를 센다.

반복 횟수 =zeroCount / 카운트가 짝수인 경우 2

반복 횟수 =(zeroCount -1)/카운트가 홀수인 경우 2

사례 2: 블록은 블록의 시작 또는 끝에서 단일 1을 가지며 나머지 값은 모두 0입니다.

반복 횟수 =zeroCount

사례 3: 블록에는 1이 없습니다. 1을 채울 수 없음을 나타내는 -1을 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include<iostream>
using namespace std;

int countIterationFill1(int arr[], int n) {
   
   bool oneFound = false;
   int iterationCount = 0;
   for (int i=0; i<n; ) {
      
      if (arr[i] == 1)
      oneFound = true;
      while (i<n && arr[i]==1)
         i++;
      int zeroCount = 0;
      while (i<n && arr[i]==0) {
         zeroCount++;
         i++;
      }
      if (oneFound == false && i == n)
         return -1;
      int itrCount;
      if (i < n && oneFound == true) {
         
         if (zeroCount & 1 == 0)
            itrCount = zeroCount/2;
         else
            itrCount = (zeroCount+1)/2;
         zeroCount = 0;
      }
      else{
         
         itrCount = zeroCount;
         zeroCount = 0;
      }
      iterationCount = max(iterationCount, itrCount);
   }

   return iterationCount;
}

int main() {
   
   int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The number of iterations to fill 1's is "<<countIterationFill1(arr, n);
   return 0;
}

출력 -

The number of iterations to fill 1's is 2