Programme C++ pour calculer le coût total requis pour qu'un robot effectue un voyage dans une grille

Supposons que nous ayons une grille de taille h x l. Chaque cellule de la grille contient un entier positif. Il existe maintenant un robot de recherche de chemin placé sur une cellule spécifique (p, q) (où p est le numéro de ligne et q est le numéro de colonne) et il peut se déplacer vers la cellule (i, j). L'opération de déplacement a un coût spécifique égal à |p - i| + |q - j|. Il existe désormais q voyages avec les propriétés suivantes.

• Chaque trajet a deux valeurs (x, y) et a une valeur commune d.

• Le robot est placé sur une cellule de valeur x puis se déplace vers une autre cellule de valeur x + d.

• Ensuite, il se déplace vers une autre cellule avec la valeur x + d + d. Ce processus se poursuivra jusqu'à ce que le robot atteigne une cellule avec une valeur supérieure ou égale à y.

• y - x est un multiple de d.

Compte tenu de ces déplacements, il faut trouver le coût total de chaque déplacement. Si le robot ne peut pas bouger, le coût du déplacement est de 0.

Donc, si l'entrée est h = 3, w = 3, d = 3, q ​​​​= 1, grille = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9 }} , trips = {{3, 9}}, alors la sortie sera 4.

3 sur cellule (2, 2)

6 sur cellule (1, 2)

9 sur cellule (3, 3)

Coût total = | (3-1) + (3-2) = 4.

Pour résoudre ce problème, nous suivrons les étapes suivantes :

Define one map loc
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:
      loc[grid[i, j]] := new pair(i, j)
Define an array dp[d + 1]
for initialize i := 1, when i <= d, update (increase i by 1), do:
   j := i
   while j < w * h, do:
      n := j + d
      if j + d > w * h, then:
      Come out from the loop
   dx := |first value of loc[n] - first value of loc[j]|
   dy := |second value of loc[n] - second value of loc[j]|
   j := j + d
   insert dx + dy at the end of dp[i]
for initialize j := 1, when j < size of dp[i], update (increase j by 1), do:
   dp[i, j] := dp[i, j] + dp[i, j - 1]
for initialize i := 0, when i < q, update (increase i by 1), do:
   tot := 0
   le := first value of trips[i]
   ri := second value of trips[i]
   if ri mod d is same as 0, then:
      f := d
   Otherwise,
         f := ri mod d
   pxl := (le - f) / d
   pxr := (ri - f) / d
   if le is same as f, then:
    if ri is same as f, then:
      tot := 0
   Otherwise
      tot := tot + (dp[f, pxr - 1] - 0)
   Otherwise
      if ri is same as f, then:
            tot := 0
  Otherwise
tot := tot + dp[f, pxr - 1] - dp[f, pxl - 1]
print(tot)

Voyons l'implémentation ci-dessous pour une meilleure compréhension −

Exemple

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve(int h, int w, int d, int q, vector<vector<int>> grid,
vector<pair<int, int>> trips) {
   map<int, pair<int, int>> loc;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++)
         loc[grid[i][j]] = make_pair(i, j);
   }
   vector<int> dp[d + 1];
   for (int i = 1; i <= d; i++) {
      int j = i;
      while (j < w * h) {
         int n = j + d;
          if (j + d > w * h)
             break;
             int dx = abs(loc[n].first - loc[j].first);
             int dy = abs(loc[n].second - loc[j].second);
             j += d;
             dp[i].push_back(dx + dy);
      }
      for (j = 1; j < dp[i].size(); j++)
        dp[i][j] += dp[i][j - 1];
   }
   for (int i = 0; i < q; i++) {
      int tot = 0;
      int le, ri;
      le = trips[i].first;
      ri = trips[i].second;
      int f;
      if (ri % d == 0)
         f = d;
      else
         f = ri % d;
      int pxl, pxr;
      pxl = (le - f) / d;
      pxr = (ri - f) / d;
      if (le == f){
         if (ri == f)
            tot = 0;
         else
            tot += (dp[f][pxr - 1] - 0);
      } else {
         if (ri == f)
            tot = 0;
         else
            tot += dp[f][pxr - 1] - dp[f][pxl - 1];
      }
      cout<< tot << endl;
    }
}
int main() {
   int h = 3, w = 3, d = 3, q = 1;
   vector<vector<int>> grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}};
   vector<pair<int, int>> trips = {{3, 9}};
   solve(h, w, d, q, grid, trips);
   return 0;
}

Input

3, 3, 3, 1, {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, {{3, 9}}

Output

4

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!