C++ प्रोग्राम: ग्रिड में रोबोट की यात्रा का कुल खर्च ज्ञात करना

समस्या विवरण

हमें h x w आयाम का एक ग्रिड दिया गया है। ग्रिड के प्रत्येक सेल में एक धनात्मक पूर्णांक है। एक पथ-खोज रोबोट एक विशेष सेल (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) पर है (1-आधारित इंडेक्सिंग)
• 6 सेल (1, 2) पर है
• 9 सेल (3, 3) पर है
• कुल लागत = |(1-2) + (2-2)| + |(3-1) + (3-2)| = 1 + 3 = 4

हल का दृष्टिकोण

1. मानचित्र बनाएं प्रत्येक मान की स्थिति संग्रहीत करने के लिए: loc[value] = (row, col)
2. प्रीकंप्यूट dp सरणी प्रत्येक शेष वर्ग (1 से d) के लिए:
   • प्रत्येक प्रारंभिक मान i (1 ≤ i ≤ d) के लिए, अनुक्रम i, i+d, i+2d, ... की गणना करें
   • लगातार पदों के बीच की दूरी संग्रहीत करें
   • त्वरित रेंज क्वेरी के लिए उपसर्ग योग बनाएं
3. प्रत्येक क्वेरी का उत्तर दें O(1) में उपसर्ग योग का उपयोग करके

एल्गोरिदम

// 1. सभी मानों की स्थिति मानचित्रित करें
for i in 0..h-1:
    for j in 0..w-1:
        loc[grid[i][j]] = (i, j)

// 2. प्रत्येक शेष वर्ग के लिए dp बनाएं
for r in 1..d:
    for val = r; val + d <= h*w; val += d:
        next = val + d
        dist = |loc[next].row - loc[val].row| + |loc[next].col - loc[val].col|
        dp[r].push_back(dist)
    // उपसर्ग योग बनाएं
    for i in 1..dp[r].size()-1:
        dp[r][i] += dp[r][i-1]

// 3. क्वेरी का उत्तर दें
for each query (x, y):
    r = (y % d == 0) ? d : y % d
    left_idx = (x - r) / d
    right_idx = (y - r) / d - 1
    if left_idx < 0: answer = dp[r][right_idx]
    else: answer = dp[r][right_idx] - dp[r][left_idx]

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

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<vector<int>> dp(d + 1);
    for (int r = 1; r <= d; r++) {
        for (int val = r; val + d <= h * w; val += d) {
            int next = val + d;
            int dx = abs(loc[next].first - loc[val].first);
            int dy = abs(loc[next].second - loc[val].second);
            dp[r].push_back(dx + dy);
        }
        for (int i = 1; i < dp[r].size(); i++) {
            dp[r][i] += dp[r][i-1];
        }
    }
    
    for (int i = 0; i < q; i++) {
        int x = trips[i].first;
        int y = trips[i].second;
        
        int r = (y % d == 0) ? d : y % d;
        int left_idx = (x - r) / d;
        int right_idx = (y - r) / d - 1;
        
        int ans = 0;
        if (left_idx < 0) {
            ans = (right_idx >= 0) ? dp[r][right_idx] : 0;
        } else {
            ans = dp[r][right_idx] - dp[r][left_idx];
        }
        cout << ans << 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

जटिलता विश्लेषण

• प्रीकंप्यूटेशन: O(h × w)
• प्रति क्वेरी: O(1)
• कुल समय: O(h × w + q)
• स्पेस: O(h × w)