मान लीजिए, हमें आयाम h x w का एक ग्रिड दिया गया है। ग्रिड में प्रत्येक सेल में कुछ सकारात्मक पूर्णांक संख्या होती है। अब एक विशेष सेल (p, q) पर एक पथ-खोज रोबोट रखा गया है (जहाँ p पंक्ति संख्या है और q सेल की स्तंभ संख्या है) और इसे सेल (i, j) में ले जाया जा सकता है। एक चाल संचालन की एक विशेष लागत होती है, जो |p - i| . के बराबर होती है + |क्यू - जे|। अब q संख्या में ट्रिप हैं, जिनमें निम्नलिखित गुण हैं।
-
प्रत्येक यात्रा के दो मान (x, y) होते हैं और एक सामान्य मान d होता है।
-
एक रोबोट को x मान वाले सेल पर रखा जाता है, फिर x + d मान वाले दूसरे सेल में चला जाता है।
-
फिर यह दूसरे सेल में चला जाता है जिसका मान x + d + d है। यह प्रक्रिया तब तक जारी रहेगी जब तक रोबोट उस सेल तक नहीं पहुंच जाता जिसका मान y से अधिक या उसके बराबर है।
-
y - x, d का गुणज है।
यात्राओं को देखते हुए, हमें प्रत्येक यात्रा की कुल लागत का पता लगाना है। यदि रोबोट नहीं चल सकता है, तो यात्रा की लागत 0 है।
इसलिए, यदि इनपुट h =3, w =3, d =3, q =1, ग्रिड ={{2, 6, 8}, {7, 3, 4}, {5, 1, 9}} जैसा है। , ट्रिप ={{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