ホームページ > バックエンド開発 > C++ > すべてのセルを黒に変換するのに必要な反復回数を求める C++ プログラム

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

王林
リリース: 2023-08-25 18:54:31
転載
1072 人が閲覧しました

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

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

  • 各白セルを黒セルに変換し、黒セルと辺を共有します。グリッドのすべてのセルが黒になるまでこれを繰り返します。

  • グリッドのすべてのセルを黒に変換するのに必要な反復回数を計算します。スターティング グリッドには黒のセルが 1 つ含まれている必要があります。

つまり、入力が h = 4、w = 4、grid = {"#..." 、 ".#.." 、 "...." のようなものである場合、 、 "...#"}

#. . .
. #. .
. . . .
##. . .
その場合、出力は 3 になります。

すべてのセルを黒に変換するには 3 回の反復が必要です。

手順

この問題を解決するには、次の手順に従います-

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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)

ログイン後にコピー

理解を深めるために、以下の実装を見てみましょう-

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

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

}

ログイン後にコピー

入力

1

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

ログイン後にコピー

出力

1

3

ログイン後にコピー

以上がすべてのセルを黒に変換するのに必要な反復回数を求める C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート