如果机器人想要移动到的单元格位于当前单元格的垂直或水平相邻位置，机器人可以直接从一个单元格走到另一个单元格。
机器人可以跳到以其当前位置为中心的 5x5 区域中的任何单元格。
机器人只能移动到不包含障碍物的网格中的另一个单元格。机器人也不能离开网格。
我们需要找出机器人到达目标所需的跳数。
因此，如果输入为 h = 4，w = 4，c = {2, 1}，d = {4, 4}，initgrid = {#..., .##., ...#, ..#.}，那么输出将为 1。机器人只需要一次跳跃就可以到达目的地。
为了解决这个问题，我们将按照以下步骤进行：
n:= 100define 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 < wdefine 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. otherwiseinsert node containing values ({nx, ny, dst[nx, ny]}) at the end of doubleq.s := ct := 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 100int 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
以上就是c++程序用于找出机器人在网格中到达特定单元所需的跳跃次数的详细内容。