Giả sử, chúng ta được cung cấp một lưới có kích thước h x w. Mỗi ô trong lưới chứa một số số nguyên dương. Bây giờ, có một robot tìm đường được đặt trên một ô cụ thể (p, q) (trong đó p là số hàng và q là số cột của một ô) và nó có thể được di chuyển đến ô (i, j). Một hoạt động di chuyển có một chi phí cụ thể, bằng | p - i | + | q - j |. Bây giờ có q số chuyến đi, có các đặc tính sau.
-
Mỗi chuyến đi có hai giá trị (x, y) và có một giá trị chung d.
-
Robot được đặt trên ô có giá trị x, sau đó di chuyển sang ô khác có giá trị x + d.
-
Sau đó, nó di chuyển đến một ô khác có giá trị x + d + d. Quá trình này sẽ tiếp tục cho đến khi rô bốt đến ô có giá trị lớn hơn hoặc bằng y.
-
y - x là bội số của d.
Với các chuyến đi, chúng ta phải tìm ra tổng chi phí của mỗi chuyến đi. Nếu rô bốt không thể di chuyển, chi phí chuyến đi là 0.
Vì vậy, nếu đầu vào là h =3, w =3, d =3, q =1, grid ={{2, 6, 8}, {7, 3, 4}, {5, 1, 9}} , chuyến đi ={{3, 9}}, thì kết quả đầu ra sẽ là 4.
3 nằm trên ô (2, 2)
6 nằm trên ô (1, 2)
9 nằm trên ô (3, 3)
Tổng chi phí =| (1 - 2) + (2 - 2) | + | (3 - 1) + (3 - 2) | =4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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;
} Đầu vào
3, 3, 3, 1, {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, {{3, 9}} Đầu ra
4