資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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 <= 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
更新於：2022年2月25日
瀏覽量：135
廣告