C ++程序找出到达网格中另一个未阻塞单元格的未阻塞单元格的最大移动次数
假设，我们有一个维度为 h * w 的网格，其中包含两种类型的单元格，阻塞的和未阻塞的。阻塞的单元格意味着单元格不可访问，而未阻塞的单元格意味着单元格是可访问的。我们在二维数组中表示网格，其中被阻塞的单元格以“#”给出，未阻塞的单元格以“.”给出。现在，我们必须从一个未阻塞的单元格到达网格中另一个未阻塞的单元格。我们只能执行两个动作，我们可以垂直移动，也可以水平移动。我们不能沿对角线移动。我们必须记住，我们只能移动到未阻塞的单元格。因此，我们必须找出从网格中另一个未阻塞单元格到达一个未阻塞单元格所需的最大移动次数。
所以，如果输入像 h = 4, w = 4, grid = {"..#.", "#.#.", "..##", "###."}，那么输出将是 4。
从单元格 (0,0) 开始，最多需要 4 次移动才能到达单元格 (2, 0)。
为了解决这个问题，我们将遵循以下步骤 -
Define an array xdir of size: 4 := {1, 0, - 1, 0}Define an array ydir of size: 4 := {0, 1, 0, - 1}
Define one 2D array dist
Define one 2D array reset
res := 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:
dist := reset
if grid[i, j] is same as '.', then:
dist[i, j] := 0
Define one queue q containing integer pairs
insert make_pair(i, j) into q
while (not q is empty), do:
x := first element of the leftmost element in the q
y := second element of the leftmost element in the q
res := maximum of (dist[x, y] and res)
delete leftmost element from q
for initialize k := 0, when k < 4, update (increase k by 1), do:
px := x + xdir[k]
py := y + ydir[k]
if px >= 0 and px < h and py >= 0 and py < w, then:
if grid[px, py] is same as '.', then:
if dist[px, py] is same as -1, then:
dist[px, py] := dist[x, y] + 1
insert pair(px, py) into q
return res
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>using namespace std;
int solve(int h, int w, vector<string> grid){
int xdir[4] = {1, 0, -1, 0};
int ydir[4] = {0, 1, 0, -1};
vector<vector<int>> dist(h, vector<int>(w, -1));
vector<vector<int>> reset(h, vector<int>(w, -1));
int res = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
dist = reset;
if(grid[i][j] == '.'){
dist[i][j] = 0;
queue<pair<int,int>> q;
q.push(make_pair(i, j));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
res = max(dist[x][y], res);
q.pop();
for(int k = 0; k < 4; k++){
int px = x + xdir[k];
int py = y + ydir[k];
if(px >= 0 && px < h && py >= 0 && py < w){
if(grid[px][py] == '.'){
if(dist[px][py] == -1){
dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
}
}
}
}
}
}
}
}
return res;
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"..#.", "#.#.", "..##", "###."};
cout << solve(h, w, grid);
return 0;
}
输入
4, 4, {"..#.", "#.#.", "..##", "###."}输出结果4
以上是 C ++程序找出到达网格中另一个未阻塞单元格的未阻塞单元格的最大移动次数 的全部内容， 来源链接： utcz.com/z/297209.html
