筆記:【演算法新手村】[初階]筆記06 - 差分(二維)

題目

在 n × n 的格子上有 m 個地毯。給出這些地毯的信息，問每個點被多少個地毯覆蓋。

• Input
  第一行，兩個正整數 n,m。意義如題所述。
  接下來 m 行，每行兩個坐標
  (x1,y1)和 (x2,y2)，代表一塊地毯，左上角是
  (x1,y1)，右下角是 (x2,y2)。

• Output
  輸出 n 行，每行 n 個正整數。
  第 i 行第 j 列的正整數表示 (i,j) 這個格子被多少個地毯覆蓋。

解題思路

顯然，地毯蓋上去代表那一個區塊被一塊地毯蓋住 (??? ，我們可以將其 想像/轉換 成對一個子矩陣做+1的操作，所以可以使用 二維差分 進行優化。

需要注意的是題目給的座標是 1-based，記得陣列不能開太小。

程式碼實作 (C++)

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n , m;

    cin >> n >> m;
    vector<vector<long long>> arr(n+2 , vector<long long>(n+2,0));

    int x1 , y1 , x2 , y2;
    for(int i = 0 ; i < m ; i++){
        cin >> x1 >> y1 >> x2 >> y2;

        arr[x1][y1]++;
        arr[x1][y2+1]--;
        arr[x2+1][y1]--;
        arr[x2+1][y2+1]++;
    }

    for(int i = 1 ; i < n+1 ; i++){
        for(int j = 1 ; j < n+1 ; j++){
            arr[i][j] =  arr[i][j] + arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1];
            cout << arr[i][j] << (j == n ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}