假设,我们有一个包含两种类型单元格的网格;黑细胞和白细胞。黑色单元格表示为“#”,白色单元格表示为“.”。网格以字符串数组形式提供给我们。现在,我们必须执行以下操作。
我们将每个白色单元格转换为黑色单元格,并与黑色单元格共享一侧。我们执行此操作,直到网格的每个单元格都变成黑色。
我们计算将网格的所有单元格转换为黑色所需的迭代次数。一开始的网格必须包含一个黑色单元格。
因此,如果输入类似于 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
以上是C++程序以找出将所有单元格转换为黑色所需的迭代次数的详细内容。更多信息请关注PHP中文网其他相关文章!