โปรแกรม 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, grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, trips = {{3, 9}} ผลลัพธ์จะเป็น 4

3 อยู่ที่เซลล์ (2, 2)

6 อยู่ที่เซลล์ (1, 2)

9 อยู่ที่เซลล์ (3, 3)

ค่าใช้จ่ายรวม = |(1 - 2) + (2 - 2)| + |(3 - 1) + (3 - 2)| = 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ -

กำหนดแมป loc สำหรับ i := 0, เมื่อ i < h, เพิ่ม i ขึ้นทีละ 1, ทำ:
  สำหรับ j := 0, เมื่อ j < w, เพิ่ม j ขึ้นทีละ 1, ทำ:
    loc[grid[i, j]] := คู่ใหม่(i, j)
กำหนดอาร์เรย์ dp[d + 1]
สำหรับ i := 1, เมื่อ i <= d, เพิ่ม i ขึ้นทีละ 1, ทำ:
  j := i
  while j < w * h, ทำ:
    n := j + d
    ถ้า j + d > w * h, แล้ว:
      ออกจากลูป
    dx := |ค่าแรกของ loc[n] - ค่าแรกของ loc[j]|
    dy := |ค่าที่สองของ loc[n] - ค่าที่สองของ loc[j]|
    j := j + d
    ใส่ dx + dy ที่ท้ายของ dp[i]
สำหรับ j := 1, เมื่อ j < ขนาดของ dp[i], เพิ่ม j ขึ้นทีละ 1, ทำ:
  dp[i, j] := dp[i, j] + dp[i, j - 1]
สำหรับ i := 0, เมื่อ i < q, เพิ่ม i ขึ้นทีละ 1, ทำ:
  tot := 0
  le := ค่าแรกของ trips[i]
  ri := ค่าที่สองของ trips[i]
  ถ้า ri mod d เท่ากับ 0, แล้ว:
    f := d
  มิฉะนั้น
    f := ri mod d
  pxl := (le - f) / d
  pxr := (ri - f) / d
  ถ้า le เท่ากับ f, แล้ว:
    ถ้า ri เท่ากับ f, แล้ว:
      tot := 0
    มิฉะนั้น
      tot := tot + (dp[f, pxr - 1] - 0)
  มิฉะนั้น
    ถ้า ri เท่ากับ f, แล้ว:
      tot := 0
    มิฉะนั้น tot := tot + dp[f, pxr - 1] - dp[f, pxl - 1]
พิมพ์(tot)

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

เอาต์พุต

4