C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

すべてのセルを黒に変換するために必要な反復回数を調べるC++プログラム


2種類のセルを含むグリッドが与えられたとします。黒い細胞、そして白い細胞。黒いセルは「#」で表され、白いセルは「。」で表されます。グリッドは文字列の配列で提供されます。ここで、次のことを実行する必要があります。

  • 各白いセルを、黒いセルと共有する側を持つ黒に変換します。グリッドのすべてのセルが黒くなるまで、この操作を実行します。

  • グリッドのすべてのセルを黒に変換するのにかかる反復回数を数えます。開始時のグリッドには、1つの黒いセルが含まれている必要があります。

したがって、入力が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, {"#...", ".#.." , "....", "...#"}

出力

3

  1. グリッド内の照らされたセルの数を見つけるためのC++プログラム

    次元h*wのグリッドが与えられていると仮定します。グリッド内のセルには、球根または障害物のいずれかを含めることができます。電球のセルはそれ自体とその右、左、上、下のセルを照らし、障害物のセルが光を遮らない限り、光はセルを通して輝くことができます。障害物セルは照明できず、電球セルからの光が他のセルに到達するのを防ぎます。したがって、配列「bulb」内のグリッド内の電球セルの位置と配列「obstacles」内の障害物セルの位置を考えると、照らされているグリッド内のセルの総数を見つける必要があります。 したがって、入力がh =4、w =4、bulb ={{1、1}、{2、2}、{3、3}}、障害物

  2. パスを作成するためにグリッドでブロックするセルの数を見つけるためのC++プログラム

    次元h*wのグリッドがあるとします。セル位置(0、0)にロボットがあり、その位置(h-1、w-1)に移動する必要があります。グリッドには、ブロックされたセルとブロックされていないセルの2種類のセルがあります。ロボットはブロックされていないセルを通過できますが、ブロックされたセルを通過することはできません。ロボットは4つの方向に進むことができます。左、右、上、下に移動できます。ただし、ロボットはセルから別のセルに任意の方向に移動する可能性があるため(前のセルを無視して)、1つのパスのみを作成し、そのパスにない他のすべてのセルをブロックする必要があります。 (0、0)から(h -1、w -1)まで