सभी कोशिकाओं को काले रंग में बदलने के लिए आवश्यक पुनरावृत्तियों की संख्या का पता लगाने के लिए 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 '#', 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)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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] == '#') {
            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;
}

इनपुट

4, 4, {"#...", ".#.." , "....", "...#"}