Chương trình C++ tính tổng chi phí robot di chuyển trên lưới

Mô tả bài toán

Cho lưới kích thước h x w, mỗi ô chứa số nguyên dương. Robot bắt đầu tại ô có giá trị x, di chuyển đến ô có giá trị x+d, rồi x+2d... cho đến khi giá trị ≥ y (với y-x chia hết cho d). Chi phí mỗi bước = khoảng cách Manhattan giữa hai ô. Tính tổng chi phí cho mỗi truy vấn.

Ví dụ

h=3, w=3, d=3, q=1, grid={{2,6,8},{7,3,4},{5,1,9}}, trips={{3,9}} → Output: 4.

Giải thích: 3 tại (2,2) → 6 tại (1,2) chi phí 1 → 9 tại (3,3) chi phí 3. Tổng = 4.

Giải thuật

1. Lưu vị trí của mỗi giá trị trong bản đồ loc.
2. Tính trước mảng prefix sum dp[i] cho mỗi dư modulo d: chi phí tích lũy từ i đến i+d, i+2d...
3. Với truy vấn (x,y): xác định dư f, chỉ số bắt đầu/kết thúc trong dp[f], trả về hiệu prefix sum.

Mã nguồn C++

#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]] = {i,j};

    vector<int> dp[d+1];
    for (int i=1; i<=d; i++) {
        for (int j=i; j<w*h; j+=d) {
            int n = j+d;
            if (n > w*h) break;
            int dx = abs(loc[n].first - loc[j].first);
            int dy = abs(loc[n].second - loc[j].second);
            dp[i].push_back(dx+dy);
        }
        for (int j=1; j<dp[i].size(); j++)
            dp[i][j] += dp[i][j-1];
    }

    for (auto [le, ri] : trips) {
        int f = (ri % d == 0) ? d : ri % d;
        int pxl = (le - f) / d;
        int pxr = (ri - f) / d;
        int tot = 0;
        if (le == f) {
            if (ri != f) tot = dp[f][pxr-1];
        } else {
            if (ri != f) tot = dp[f][pxr-1] - dp[f][pxl-1];
        }
        cout << tot << '\n';
    }
}

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 / Đầu ra

Input: 3, 3, 3, 1, {{2,6,8},{7,3,4},{5,1,9}}, {{3,9}}
Output: 4