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。

要解决这个问题，我们将按照以下步骤进行：

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 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)登录后复制

示例

#include using namespace std; const int INF = 1e9; void solve(int h, int w, int d, int q, vector grid, vector trips) { map loc; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) loc[grid[i][j]] = make_pair(i, j); } vector dp[d + 1]; for (int i = 1; i 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