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

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])

Copy after login

Example

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

#include  using namespace std; const int INF = 1e9; #define N 100 int h, w; pair 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 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 c, pair 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 c = {2, 1}, d = {4, 4}; string initGrid[] = {"#...", ".##.", "...#", "..#."}; solve(c, d, initGrid); return 0; }

Copy after login

Input

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

Copy after login

Output

Copy after login

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!