数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序找出网格中从一个未阻塞单元格到另一个未阻塞单元格的最大移动次数
假设，我们给定一个维度为h * w的网格，其中包含两种类型的单元格，阻塞的和未阻塞的。阻塞的单元格表示该单元格不可访问，未阻塞的表示该单元格可访问。我们用一个二维数组表示网格，其中阻塞的单元格用“#”表示，未阻塞的单元格用“.”表示。现在，我们必须从网格中的一个未阻塞单元格到达另一个未阻塞单元格。我们只能执行两种移动，我们可以垂直移动或水平移动。我们不能对角移动。我们必须记住，我们只能移动到未阻塞的单元格。因此，我们必须找出在网格中从一个未阻塞单元格到达另一个未阻塞单元格所需的最大移动次数。
因此，如果输入类似于h = 4，w = 4，grid = {"..#.", "#.#.", "..##", "###."}，则输出将为4。
从单元格(0,0)开始，到达单元格(2, 0)最多需要4次移动。
为了解决这个问题，我们将遵循以下步骤 -
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
更新于: 2022年3月2日
258 次浏览
广告