假设我们有一个 h x w 的网格。网格在一个名为 'initGrid' 的二维数组中表示，其中网格中的每个单元格都用 '#' 或 '.' 表示。 '#' 表示网格中有障碍物，'.' 表示该单元格上有一条路径。现在，一个机器人被放置在网格上的一个单元格 'c' 上，该单元格具有行号 x 和列号 y。机器人必须从一个具有行号 p 和列号 q 的单元格 'd' 移动到另一个单元格。单元格坐标 c 和 d 都以整数对的形式给出。现在，机器人可以按以下方式从一个单元格移动到另一个单元格：
如果机器人想要移动到的单元格位于当前单元格的垂直或水平相邻位置，机器人可以直接从一个单元格走到另一个单元格。
机器人可以跳到以其当前位置为中心的 5x5 区域中的任何单元格。
-
机器人只能移动到不包含障碍物的网格中的另一个单元格。机器人也不能离开网格。
立即学习“C++免费学习笔记（深入）”；
我们需要找出机器人到达目标所需的跳数。
因此，如果输入为 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])Example
让我们看下面的实现以获得更好的理解−
#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
