假设我们有一个尺寸为 h x w 的网格。网格中的每个单元格包含一个正整数。现在有一个路径查找机器人放置在特定的单元格（p，q）上（其中 p 是行号，q 是列号），它可以移动到单元格（i，j）。移动操作有一个特定的成本，等于 |p – i| + |q – j|。现在有 q 个旅行，具有以下属性。
每个旅行有两个值（x，y），并且有一个共同的值 d。
机器人放置在一个值为 x 的单元格上，然后移动到另一个值为 x + d 的单元格。
然后它移动到另一个值为 x + d + d 的单元格。这个过程将继续，直到机器人到达一个值大于或等于 y 的单元格。
立即学习“C++免费学习笔记（深入）”；
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 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让我们看下面的实现以更好地理解 −
示例
#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 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 > grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}; vector> 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}}登录后复制
输出
4登录后复制
以上就是C++程序用于计算机器人在网格中完成一次行程所需的总成本的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2587955.html
