Programme C++ pour trouver le nombre d'itérations requis pour convertir toutes les cellules en noir

Supposons que nous ayons une grille contenant deux types de cellules : les globules noirs et les globules blancs. Les cellules noires sont représentées par « # » et les cellules blanches sont représentées par « ». La grille nous est fournie sous forme d’un tableau de chaînes. Nous devons maintenant faire ce qui suit.

• Nous convertissons chaque cellule blanche en cellule noire et partageons un côté avec la cellule noire. Nous faisons cela jusqu'à ce que chaque cellule de la grille devienne noire.

• Nous calculons le nombre d'itérations nécessaires pour convertir toutes les cellules de la grille en noir. La grille de départ doit contenir une case noire.

Donc, si l'entrée est quelque chose comme h = 4, w = 4, grid = {"#..." , ".#.." , "....", "...#"}

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

Ensuite, la sortie sera 3.

Il faut 3 itérations pour convertir toutes les cellules en noir.

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes -

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)

Exemple

Voyons l'implémentation ci-dessous pour une meilleure compréhension −

#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;
}

Input

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

Output

3

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!