Program C++ untuk mencari bilangan lompatan yang diperlukan oleh robot untuk mencapai sel tertentu dalam grid

Andaikan kita mempunyai grid h x w. Grid diwakili dalam tatasusunan dua dimensi yang dipanggil 'initGrid', di mana setiap sel dalam grid diwakili oleh '#' atau '.'. '#' bermaksud terdapat halangan dalam grid, '.' bermakna terdapat laluan pada sel tersebut. Kini, robot diletakkan pada sel 'c' pada grid, yang mempunyai nombor baris x dan nombor lajur y. Robot perlu bergerak dari sel 'd' dengan nombor baris p dan nombor lajur q ke sel lain. Koordinat sel c dan d kedua-duanya diberikan sebagai pasangan integer. Kini robot boleh bergerak dari satu sel ke sel lain seperti berikut:

• Jika sel yang robot ingin alihkan terletak secara menegak atau mendatar bersebelahan dengan sel semasa, robot boleh berjalan terus dari satu sel ke sel yang lain.

• Robot boleh melompat ke mana-mana sel dalam kawasan 5x5 berpusat pada lokasi semasanya.

• Robot hanya boleh bergerak ke sel lain dalam grid yang tidak mengandungi halangan. Robot juga tidak boleh meninggalkan grid.

Kita perlu mengetahui bilangan lompatan yang diperlukan untuk robot mencapai sasaran.

Jadi, jika input ialah h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##." , "...#", "..#."}, maka outputnya ialah 1. Robot hanya memerlukan satu lompatan untuk sampai ke destinasinya.

Untuk menyelesaikan masalah ini, kami akan mengikuti langkah berikut:

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

Contoh

Mari kita lihat pelaksanaan di bawah untuk mendapatkan pemahaman yang lebih baik −#🎜🎜 #

#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

Atas ialah kandungan terperinci Program C++ untuk mencari bilangan lompatan yang diperlukan oleh robot untuk mencapai sel tertentu dalam grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!