모든 셀을 검정색으로 변환하는 데 필요한 반복 횟수를 찾는 C++ 프로그램-C++-php.cn

모든 셀을 검정색으로 변환하는 데 필요한 반복 횟수를 찾는 C++ 프로그램

王林

풀어 주다： 2023-08-25 18:54:31

앞으로

969명이 탐색했습니다.

모든 셀을 검정색으로 변환하는 데 필요한 반복 횟수를 찾는 C++ 프로그램

흑색 세포와 백혈구 두 가지 유형의 세포가 포함된 그리드가 있다고 가정해 보겠습니다. 검은색 셀은 "#"으로 표시되고 흰색 셀은 "."으로 표시됩니다. 그리드는 문자열 배열로 제공됩니다. 이제 우리는 다음을 수행해야 합니다.

흰색 셀을 각각 검은색 셀로 변환하고 한쪽을 검은색 셀과 공유합니다. 그리드의 모든 셀이 검은색으로 변할 때까지 이 작업을 수행합니다.
그리드의 모든 셀을 검정색으로 변환하는 데 필요한 반복 횟수를 계산합니다. 시작 그리드에는 하나의 검은색 셀이 포함되어야 합니다.

입력이 h = 4, w = 4, Grid = {"#..." , ".#.." , "....", "...#"}

#	.	.	.
.	#		.
.	.	.	.
.	.	.	#

그러면 출력은 3이 됩니다.

모든 셀을 검은색으로 변환하려면 3번의 반복이 필요합니다.

단계

이 문제를 해결하기 위해 다음 단계를 따르겠습니다. -

Define an array dx of size: 4 containing := { 1, 0, - 1, 0 }
Define an array dy of size: 4 containing := { 0, 1, 0, - 1 }
Define one 2D array distance
Define one queue q that contain integer pairs
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as &#39;#&#39;, then:
         distance[i, j] := 0
         insert one pair(i, j) into q
while (not q is empty), do:
   first element of auto now = q
   delete element from q
   for initialize dir := 0, when dir < 4, update (increase dir by 1), do:
      cx := first value of now + dx[dir]
      cy := second value of now + dy[dir]
      if cx < 0 or cx >= h or cy < 0 or cy >= w, then:
         if distance[cx, cy] is same as -1, then:
            distance[cx, cy] := distance[first value of now, second value of now] + 1
         insert one pair (cx, cy) into q
ans := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      ans := maximum of ans and distance[i, j]
print(ans)

로그인 후 복사

Example

더 나은 이해를 위해 아래 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

void solve(int h, int w, vector <string> grid){
   int dx[4] = { 1, 0, -1, 0 };
   int dy[4] = { 0, 1, 0, -1 };
   vector<vector<int>> distance(h, vector<int>(w, -1));
   queue<pair<int, int>> q;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == &#39;#&#39;) {
            distance[i][j] = 0;
            q.push(pair<int, int>(i,j));
         }
      }
   }
   while (!q.empty()) {
      auto now = q.front();
      q.pop();
      for (int dir = 0; dir < 4; dir++) {
         int cx = now.first + dx[dir];
         int cy = now.second + dy[dir];
         if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue;
         if (distance[cx][cy] == -1) {
            distance[cx][cy] = distance[now.first][now.second] + 1;
            q.push(pair<int, int> (cx, cy));
         }
      }
   }
   int ans = 0; for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
         ans = max(ans, distance[i][j]);
      }
   }
   cout << ans << endl;
}
int main() {
   int h = 4, w = 4; vector<string>
   grid = {"#...", ".#.." , "....", "...#"};
   solve(h, w, grid);
   return 0;
}

로그인 후 복사