C++ 程序找出机器人在网格中旅行所需的总成本
假设给定一个尺寸为 hx 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 locfor 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)
让我们看看以下实现以更好地理解 -
示例
#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
以上是 C++ 程序找出机器人在网格中旅行所需的总成本 的全部内容， 来源链接： utcz.com/z/297174.html
