search
HomeBackend DevelopmentC++C++ program to find the number of jumps required by a robot to reach a specific cell in a grid

C++ program to find the number of jumps required by a robot to reach a specific cell in a grid

Suppose we have a grid of h x w. The grid is represented in a two-dimensional array called 'initGrid', where each cell in the grid is represented by a '#' or '.'. '#' means there is an obstacle in the grid, '.' means there is a path on that cell. Now, a robot is placed on a cell 'c' on the grid, which has row number x and column number y. The robot has to move from a cell 'd' with row number p and column number q to another cell. The cell coordinates c and d are both given as pairs of integers. Now the robot can move from one cell to another as follows:

  • If the cell the robot wants to move to is located vertically or horizontally adjacent to the current cell, the robot can walk directly from one cell to another.

  • The robot can jump to any cell in a 5x5 area centered on its current location.

  • The robot can only move to another cell in the grid that does not contain obstacles. The robot cannot leave the grid either.

We need to find out the number of hops it takes for the robot to reach the target.

So, if the input is h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", " ...#", "..#."}, then the output will be 1. The robot only needs one jump to reach its destination.

To solve this problem, we will follow the following steps:

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

Let us see the implementation below to get a better understanding −

#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;
}

Input

4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}

Output

1

The above is the detailed content of C++ program to find the number of jumps required by a robot to reach a specific cell in a grid. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
用于精确目标检测的多网格冗余边界框标注用于精确目标检测的多网格冗余边界框标注Jun 01, 2024 pm 09:46 PM

一、前言目前领先的目标检测器是基于深度CNN的主干分类器网络重新调整用途的两级或单级网络。YOLOv3就是这样一种众所周知的最先进的单级检测器,它接收输入图像并将其划分为大小相等的网格矩阵。具有目标中心的网格单元负责检测特定目标。今天分享的,就是提出了一种新的数学方法,该方法为每个目标分配多个网格,以实现精确的tight-fit边界框预测。研究者还提出了一种有效的离线复制粘贴数据增强来进行目标检测。新提出的方法显着优于一些当前最先进的目标检测器,并有望获得更好的性能。二、背景目标检测网络旨在使用

机器人学我表情的样子,让人感到一丝恐惧机器人学我表情的样子,让人感到一丝恐惧Apr 09, 2023 am 10:11 AM

​通常,机器人的主要功能是完成一些简单的操作任务,我们希望机器人可以模仿人,让能力尽可能接近人类水平。不论是小米的 CyberOne 还是特斯拉的 Optimus,人们关心的主要是其机械关节数量,控制算法和行走速度。不过在这个领域,有些人探索的方向更加脑洞大开:现在,有一种机器人把模仿真人表情做到了极致:先尝试一下自拍。从「嫌弃」到「惊讶」,都可以做到完全同步:​这个机器人名叫 Ameca,是个表情怪。除了模仿,它自己也能照镜子做很多小表情,看起来非常像真人。Ameca「假装」第一次见到镜子,首

拿破仑、孔子在线陪聊!AI聊天机器人「复活」历史名人,网友:真上头!拿破仑、孔子在线陪聊!AI聊天机器人「复活」历史名人,网友:真上头!Apr 08, 2023 pm 12:11 PM

和活生生的已故历史名人聊天是个什么感觉?近日,就有一群开发者利用语言模型,把千百年来各行各业的历史名人全部「复活」成了聊天机器人,做进了一款手机app里,起名叫「你好,历史」!开发者声称,这个与古代名人聊天的app涉及的内容几乎无所不包。比如可以:与玛丽莲·梦露聊好莱坞八卦与弗里达·卡洛讨论现代艺术问问圣诞老人他有多少只驯鹿问问科特·科本为什么自杀向穴居人学习如何生火与宇宙意识辩论生命的意义不过他们也没忘记提醒用户,这些对话是由人工智能生成的,所以不要太认真。而且每个对话都是独一无二的,你永远不

苹果手机中设置相机网格的操作步骤苹果手机中设置相机网格的操作步骤Mar 26, 2024 pm 07:21 PM

1、打开苹果手机的桌面,找到并点击进入【设置】,2、在设置的页面点击进入【相机】。3、点击打开【网格】右侧的开关即可。

盘点全球不错的七所机器人工程专业学校盘点全球不错的七所机器人工程专业学校Apr 08, 2023 pm 01:31 PM

有抱负的工程师应该了解世界各地著名的机器人工程学院。现在是从事机器人和工程事业的最佳时机——从人工智能到太空探索,这一领域充满了令人兴奋的创新和进步。美国劳工统计局估计,未来10年,机械工程领域的职业总体上将保持7%的稳定增长率,确保毕业生将有大量的就业机会。机器人工程专业的学生平均工资超过9万美元,无需担心还助学贷款的问题。对于那些考虑投身机器人工程领域的人来说,选择一所合适的大学是非常重要的。世界上许多顶尖的机器人工程学院都在美国,尽管国外也有一些很棒的项目。这是7所世界上最好的机器人工程学

女王登基70周年,世上首个超逼真人形机器艺术家献上肖像画作,被锐评“缺少信念”女王登基70周年,世上首个超逼真人形机器艺术家献上肖像画作,被锐评“缺少信念”Apr 08, 2023 pm 08:11 PM

大数据文摘出品作者:Caleb为庆祝英国女王伊丽莎白二世登基70周年,英国也是早早就洋溢出了庆典的味道。据了解,英国将于6月2日至5日连放4天公众假期,并在期间举行多项庆祝活动。英国皇家铸币厂也在精心打造有史以来最大的硬币,直径220毫米,重15公斤,面值15000英镑,耗时近400小时打造,是该厂1100年来生产的最大硬币。这枚金币一面雕刻着代表英国女王伊丽莎白二世的符号EⅡR,周围环绕着代表英国的玫瑰、水仙、蓟和三叶草。另一面有女王骑在马背上的图案。在这么热闹的日子里,AI当然也必须来凑一凑

让机器人学会咖啡拉花,得从流体力学搞起!CMU&amp;MIT推出流体模拟平台让机器人学会咖啡拉花,得从流体力学搞起!CMU&amp;MIT推出流体模拟平台Apr 07, 2023 pm 04:46 PM

机器人也能干咖啡师的活了!比如让它把奶泡和咖啡搅拌均匀,效果是这样的:然后上点难度,做杯拿铁,再用搅拌棒做个图案,也是轻松拿下:这些是在已被ICLR 2023接收为Spotlight的一项研究基础上做到的,他们推出了提出流体操控新基准FluidLab以及多材料可微物理引擎FluidEngine。研究团队成员分别来自CMU、达特茅斯学院、哥伦比亚大学、MIT、MIT-IBM Watson AI Lab、马萨诸塞大学阿默斯特分校。在FluidLab的加持下,未来机器人处理更多复杂场景下的流体工作也都

四足机器人学会“双腿站立下楼梯”!效率比腿式系统高83%四足机器人学会“双腿站立下楼梯”!效率比腿式系统高83%Apr 09, 2023 am 11:21 AM

​还记得那个和特斯拉飙车的机器人吗?这是瑞士苏黎世联邦理工学院衍生公司研发的与公司同名的四足轮腿式机器人——Swiss-Mile,前身是ANYmal四足机器人。距离它和特斯拉飙车还不到半年的时间,它又实现了重大升级。这次升级改进了机器人的算法,运动能力直接UP UP UP ! 可以双腿站立下楼梯:(小编内心OS:如果是我穿轮滑鞋下楼梯可能会摔个狗吃屎)楼梯爬累了,坐个电梯吧,用前脚按开电梯门:面对障碍物应对自如:它还能知道什么时候该站起来,什么时候该“趴下”,双腿直立与四足运动之间的切换更丝滑:

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool