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 = h 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)登录后复制