首页 > 后端开发 > C++ > C++程序用于找出机器人在网格中到达特定单元所需的跳跃次数

C++程序用于找出机器人在网格中到达特定单元所需的跳跃次数

WBOY
发布: 2023-09-17 19:17:02
转载
637 人浏览过

C++程序用于找出机器人在网格中到达特定单元所需的跳跃次数

假设我们有一个 h x w 的网格。网格在一个名为 'initGrid' 的二维数组中表示,其中网格中的每个单元格都用 '#' 或 '.' 表示。 '#' 表示网格中有障碍物,'.' 表示该单元格上有一条路径。现在,一个机器人被放置在网格上的一个单元格 'c' 上,该单元格具有行号 x 和列号 y。机器人必须从一个具有行号 p 和列号 q 的单元格 'd' 移动到另一个单元格。单元格坐标 c 和 d 都以整数对的形式给出。现在,机器人可以按以下方式从一个单元格移动到另一个单元格:

  • 如果机器人想要移动到的单元格位于当前单元格的垂直或水平相邻位置,机器人可以直接从一个单元格走到另一个单元格。

  • 机器人可以跳到以其当前位置为中心的 5x5 区域中的任何单元格。

  • 机器人只能移动到不包含障碍物的网格中的另一个单元格。机器人也不能离开网格。

我们需要找出机器人到达目标所需的跳数。

因此,如果输入为 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 &#39;.&#39;, 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] == &#39;.&#39;) {
               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]) << &#39;\n&#39;;
}
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++程序用于找出机器人在网格中到达特定单元所需的跳跃次数的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板