假设，我们有一个尺寸为 hx w 的网格。网格以称为“initGrid”的二维数组表示，其中网格中的每个单元格都由“#”或“.”表示。'#' 表示网格包含障碍物，'.' 意味着有一条路径通过该单元格。现在，机器人被放置在网格上的单元格“c”上，其中行号为 x，列号为 y。机器人必须前往另一个具有行号 p 和列号 q 的单元格“d”。单元坐标 c 和 d 都以整数对的形式呈现给我们。现在，机器人可以通过以下方式从一个单元移动到另一个单元 -
如果机器人想要移动到的单元格与当前所在的单元格垂直或水平相邻，则机器人可以从一个单元格走到另一个单元格。
机器人可以跳到 5×5 区域中的任何单元格，其中心位于当前所在的单元格。
如果目标单元格不包含障碍物，机器人只能移动到网格中的另一个单元格。机器人也不能离开网格。
我们必须找出到达目的地所需的跳跃次数。
所以，如果输入像 h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", ". ..#", "..#."}，则输出为 1。机器人只需跳跃一次即可到达目的地。
为了解决这个问题，我们将遵循以下步骤 -
N:= 100
Define intger pairs s and t.
Define an array grid of size: N.
Define an array dst of size: N x N.
Define a struct node that contains integer values a, b, and e.
Define a function check(), this will take a, b,
return a >= 0 AND a < h AND b >= 0 AND b < w
Define a function bfs(), this will take a, b,
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:
dst[i, j] := infinity
dst[a, b] := 0
Define one deque doubleq
Insert a node containing values {a, b, and dst[a, b]} at the end of doubleq
while (not doubleq is empty), do:
nd := first element of doubleq
if e value of nd > dst[a value of nd, b value of nd], then:
Ignore the following part, skip to the next iteration
for initialize diffx := -2, when diffx <= 2, update (increase diffx by 1), do:
for initialize diffy := -2, when diffy <= 2, update (increase diffy by 1), do:
tm := |diffx + |diffy||
nx := a value of nd + diffx, ny = b value of nd + diffy
if check(nx, ny) and grid[nx, ny] is same as '.', then:
w := (if tm > 1, then 1, otherwise 0)
if dst[a value of nd, b value of nd] + w < dst[nx, ny], then:
dst[nx, ny] := dst[a value of nd, b value of nd] + w
if w is same as 0, then:
insert node containing values ({nx, ny, dst[nx, ny]}) at the beginning of doubleq.
Otherwise
insert node containing values ({nx, ny, dst[nx, ny]}) at the end of doubleq.
s := c
t := d
(decrease first value of s by 1)
(decrease second value of s by 1)
(decrease first value of t by 1)
(decrease second value of t by 1)
for initialize i := 0, when i < h, update (increase i by 1), do:
grid[i] := initGrid[i]
bfs(first value of s, second value of s)
print(if dst[first value of t, second value of t] is same as infinity, then -1, otherwise dst[first value of t, second value of t])示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int h, w;
pair<int, int> s, t;
string grid[N];
int dst[N][N];
struct node {
int a, b, e;
};
bool check(int a, int b) {
return a >= 0 && a < h && b >= 0 && b < w;
}
void bfs(int a, int b) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
dst[i][j] = INF;
}
dst[a][b] = 0;
deque<node> doubleq;
doubleq.push_back({a, b, dst[a][b]});
while (!doubleq.empty()) {
node nd = doubleq.front();
doubleq.pop_front();
if (nd.e > dst[nd.a][nd.b])
continue;
for (int diffx = -2; diffx <= 2; diffx++) {
for (int diffy = -2; diffy <= 2; diffy++) {
int tm = abs(diffx) + abs(diffy);
int nx =nd.a+ diffx, ny =nd.b+ diffy;
if (check(nx, ny) && grid[nx][ny] == '.') {
int w = (tm > 1) ? 1 : 0;
if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
dst[nx][ny] = dst[nd.a][nd.b] + w;
if (w == 0)
doubleq.push_front({nx, ny, dst[nx][ny]});
else
doubleq.push_back({nx, ny, dst[nx][ny]});
}
}
}
}
}
}
void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){
s = c;
t = d;
s.first--, s.second--, t.first--, t.second--;
for(int i = 0; i < h; i++)
grid[i] = initGrid[i];
bfs(s.first, s.second);
cout << (dst[t.first][t.second] == INF ? -1 :
dst[t.first][t.second]) << '\n';
}
int main() {
h = 4, w = 4;
pair<int,int> c = {2, 1}, d = {4, 4};
string initGrid[] = {"#...", ".##.", "...#", "..#."};
solve(c, d, initGrid);
return 0;
}输入
4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}输出结果1
