数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究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 < 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
更新于：2022年3月2日
浏览量：188
广告