C++-Programm, um die Anzahl der Sprünge zu ermitteln, die ein Roboter benötigt, um eine bestimmte Zelle in einem Raster zu erreichen

Angenommen, wir haben ein Raster von H x B. Das Raster wird in einem zweidimensionalen Array namens „initGrid“ dargestellt, wobei jede Zelle im Raster durch ein „#“ oder „.“ dargestellt wird. „#“ bedeutet, dass sich im Gitter ein Hindernis befindet, „.“ bedeutet, dass sich in dieser Zelle ein Pfad befindet. Nun wird ein Roboter auf einer Zelle „c“ im Raster platziert, die die Zeilennummer x und die Spaltennummer y hat. Der Roboter muss sich von einer Zelle „d“ mit der Zeilennummer p und der Spaltennummer q in eine andere Zelle bewegen. Die Zellkoordinaten c und d werden beide als Ganzzahlpaare angegeben. Nun kann sich der Roboter wie folgt von einer Zelle zur anderen bewegen:

• Wenn sich die Zelle, zu der sich der Roboter bewegen möchte, vertikal oder horizontal neben der aktuellen Zelle befindet, kann der Roboter direkt von einer Zelle zur anderen gehen.

• Der Roboter kann zu jeder Zelle in einem 5x5-Bereich springen, der um seinen aktuellen Standort zentriert ist.

• Der Roboter kann sich nur zu einer anderen Zelle im Gitter bewegen, die keine Hindernisse enthält. Auch der Roboter kann das Gitter nicht verlassen.

Wir müssen herausfinden, wie viele Sprünge der Roboter braucht, um das Ziel zu erreichen.

Wenn also die Eingabe h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", ".. .#", "..#."}, dann ist die Ausgabe 1. Der Roboter braucht nur einen Sprung, um sein Ziel zu erreichen.

Um dieses Problem zu lösen, werden wir die folgenden Schritte ausführen:

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

Beispiel

Sehen wir uns die Implementierung unten an, um ein besseres Verständnis zu erhalten −

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

Eingabe

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

Ausgabe

1

Das obige ist der detaillierte Inhalt vonC++-Programm, um die Anzahl der Sprünge zu ermitteln, die ein Roboter benötigt, um eine bestimmte Zelle in einem Raster zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!