ধরি, 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-এর গুণিতক।
যাত্রাগুলো দেওয়া থাকলে, প্রতিটি যাত্রার মোট খরচ বের করতে হবে। যদি রোবট মুভ না করতে পারে, তবে যাত্রার খরচ ০ হবে।
উদাহরণস্বরূপ, ইনপুট h = 3, w = 3, d = 3, q = 1, grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, trips = {{3, 9}} হলে আউটপুট হবে ৪।
৩ হল সেল (২, ২)-এ
৬ হল সেল (১, ২)-এ
৯ হল সেল (৩, ৩)-এ
মোট খরচ = |(1 - 2) + (2 - 2)| + |(3 - 1) + (3 - 2)| = ৪।
সমাধানের পদ্ধতি
একটি map loc ডিফাইন করুন
i = 0 থেকে h-1 পর্যন্ত:
j = 0 থেকে w-1 পর্যন্ত:
loc[grid[i][j]] := new pair(i, j)
d+1 আকারের একটি dp অ্যারে ডিফাইন করুন
i = 1 থেকে d পর্যন্ত:
j := i
while j < w * h:
n := j + d
if j + d > w * h, তবে:
লুপ থেকে বের হোন
dx := |loc[n].first - loc[j].first|
dy := |loc[n].second - loc[j].second|
j := j + d
dx + dy কে dp[i]-তে যোগ করুন
j = 1 থেকে dp[i].size()-1 পর্যন্ত:
dp[i][j] := dp[i][j] + dp[i][j-1]
i = 0 থেকে q-1 পর্যন্ত:
tot := 0
le := trips[i].first
ri := trips[i].second
if ri % d == 0, তবে:
f := d
অন্যথায়:
f := ri % d
pxl := (le - f) / d
pxr := (ri - f) / d
if le == f, তবে:
if ri == f, তবে:
tot := 0
অন্যথায়:
tot := tot + (dp[f][pxr - 1] - 0)
অন্যথায়:
if ri == f, তবে:
tot := 0
অন্যথায়:
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
