로봇이 그리드에서 이동을 완료하는 데 필요한 총 비용을 계산하는 C++ 프로그램

h x w 크기의 그리드가 있다고 가정합니다. 그리드의 각 셀에는 양의 정수가 포함되어 있습니다. 이제 특정 셀(p, q)(p는 행 번호, q는 열 번호)에 경로 찾기 로봇이 배치되어 셀(i, j)로 이동할 수 있습니다. 이동 작업의 특정 비용은 |p - i| + |q - j|입니다. 이제 다음 속성을 가진 q개의 여행이 있습니다.

• 각 여행에는 두 개의 값(x, y)이 있으며 공통 값 d가 있습니다.

• 로봇은 x 값을 가진 셀에 배치된 다음 x + d 값을 가진 다른 셀로 이동합니다.

• 그런 다음 x + d + d 값을 가진 다른 셀로 이동합니다. 이 과정은 로봇이 y보다 크거나 같은 값을 갖는 셀에 도달할 때까지 계속됩니다.

• y - x는 d의 배수입니다.

이러한 여행을 고려하여 각 여행의 총 비용을 찾아야 합니다. 로봇이 움직일 수 없으면 이동 비용은 0입니다.

그러므로 입력이 h = 3, w = 3, d = 3, q ​​​​= 1, 그리드 = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9 }} , 여행 = {{3, 9}}이면 출력은 4입니다.

3 셀(2, 2)

6 셀(1, 2)

9 셀(3, 3)

총 비용 = | (1 - 2) + (2 - 2) | (3 - 1) + (3 - 2) = 4.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

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)

더 나은 이해를 위해 아래 구현을 살펴보겠습니다. −

Example

#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

위 내용은 로봇이 그리드에서 이동을 완료하는 데 필요한 총 비용을 계산하는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!