Processing math: 100%
Solutions of Manhattan distance - MarisaOJ: Marisa Online Judge

Solutions of Manhattan distance

Select solution language

Write solution here.


User Avatar nhanzzzz    Created at    18 likes

Lời giải

  • Ta nhận thấy các phần tử cách ô (i,j) không quá k sẽ tạo thành một hình thoi
  • Vì thế chúng ta cần phải xoay ma trận 45 độ để các phần tử cần tính tổng trở thành hình vuông, sau đó sử dụng prefix sum hai chiều để tìm tổng các phần tử

Xoay ma trận 45 độ:

  • Mỗi ô (i,j) trong hệ tọa độ ban đầu được ánh xạ sang hệ mới: (X=i+j,Y=ij+n)

  • Điều này giúp tất cả các ô có cùng tổng chỉ số X nằm trên cùng một đường chéo, giúp ta dễ dàng xác định phạm vi cộng dồn.

Prefix sum hai chiều:

  • Chúng ta tạo mảng prefix sum P để tính tổng nhanh với R là ma trận đã xoay 45 độ: P[x][y]=R[x][y]+P[x1][y]+P[x][y1]P[x1][y1]

  • Sau đó, tổng giá trị trong phạm vi k của một ô (i,j) được tính như sau: sum(x1,y1,x2,y2)=P[x2][y2]P[x11][y2]P[x2][y11]+P[x11][y11]

Kết luận:

  • Việc sử dụng phép xoay ma trận kết hợp với prefix sum, thì độ phức tạp sẽ là O(n2), phù hợp với giới hạn bài toán.

Code mẫu:

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

const int MX = 2005;
int n, k, a[1005][1005], r[MX][MX], p[MX][MX], res[1005][1005];

int sum(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // nhap mang va xoay 45 do
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];
            int x = i + j, y = i - j + n;
            r[x][y] = a[i][j];
        }
    }
    // xay dung prefix sum hai chieu
    for(int i = 1; i < MX; ++i){
        for(int j = 1; j < MX; ++j){
            p[i][j] = r[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
        }
    }
    // tinh tong 
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            int x = i + j, y = i - j + n;
            int x1 = max(1, x - k), y1 = max(1, y - k);
            int x2 = min(MX-1, x + k), y2 = min(MX-1, y + k);
            res[i][j] = sum(x1, y1, x2, y2);
        }
    }
    // in ket qua
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cout << res[i][j] << " ";
        }
        cout << "\n";
    }
}