


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 '.', 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] == '.') { 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; }
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!

The history and evolution of C# and C are unique, and the future prospects are also different. 1.C was invented by BjarneStroustrup in 1983 to introduce object-oriented programming into the C language. Its evolution process includes multiple standardizations, such as C 11 introducing auto keywords and lambda expressions, C 20 introducing concepts and coroutines, and will focus on performance and system-level programming in the future. 2.C# was released by Microsoft in 2000. Combining the advantages of C and Java, its evolution focuses on simplicity and productivity. For example, C#2.0 introduced generics and C#5.0 introduced asynchronous programming, which will focus on developers' productivity and cloud computing in the future.

There are significant differences in the learning curves of C# and C and developer experience. 1) The learning curve of C# is relatively flat and is suitable for rapid development and enterprise-level applications. 2) The learning curve of C is steep and is suitable for high-performance and low-level control scenarios.

There are significant differences in how C# and C implement and features in object-oriented programming (OOP). 1) The class definition and syntax of C# are more concise and support advanced features such as LINQ. 2) C provides finer granular control, suitable for system programming and high performance needs. Both have their own advantages, and the choice should be based on the specific application scenario.

Converting from XML to C and performing data operations can be achieved through the following steps: 1) parsing XML files using tinyxml2 library, 2) mapping data into C's data structure, 3) using C standard library such as std::vector for data operations. Through these steps, data converted from XML can be processed and manipulated efficiently.

C# uses automatic garbage collection mechanism, while C uses manual memory management. 1. C#'s garbage collector automatically manages memory to reduce the risk of memory leakage, but may lead to performance degradation. 2.C provides flexible memory control, suitable for applications that require fine management, but should be handled with caution to avoid memory leakage.

C still has important relevance in modern programming. 1) High performance and direct hardware operation capabilities make it the first choice in the fields of game development, embedded systems and high-performance computing. 2) Rich programming paradigms and modern features such as smart pointers and template programming enhance its flexibility and efficiency. Although the learning curve is steep, its powerful capabilities make it still important in today's programming ecosystem.

C Learners and developers can get resources and support from StackOverflow, Reddit's r/cpp community, Coursera and edX courses, open source projects on GitHub, professional consulting services, and CppCon. 1. StackOverflow provides answers to technical questions; 2. Reddit's r/cpp community shares the latest news; 3. Coursera and edX provide formal C courses; 4. Open source projects on GitHub such as LLVM and Boost improve skills; 5. Professional consulting services such as JetBrains and Perforce provide technical support; 6. CppCon and other conferences help careers

C# is suitable for projects that require high development efficiency and cross-platform support, while C is suitable for applications that require high performance and underlying control. 1) C# simplifies development, provides garbage collection and rich class libraries, suitable for enterprise-level applications. 2)C allows direct memory operation, suitable for game development and high-performance computing.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

SublimeText3 Chinese version
Chinese version, very easy to use

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

Dreamweaver CS6
Visual web development tools

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Zend Studio 13.0.1
Powerful PHP integrated development environment