2132. 用郵票貼滿網格圖

推薦事前閱讀：二維差分數組介紹, 前綴和介紹

思路

思路很簡單，遍歷所有節點，只要能放郵票，就放下去。
在放完之後，檢查版面是否有空隙，沒有空隙return true，有空隙 return false。
整個做法可以分為幾個部分

1. 檢查某個節點能不能放下郵票。
   • 假設結點在 $(x,y)$ ，就檢查以它為左上角的stampHeight x stampWidth矩形區塊。
2. 實際放下郵票。
   • 確認好所有可以放郵票的點，實際將由票貼到版面上，同樣需要將stampHeight x stampWidth的矩形區塊更新。
3. 檢查放完郵票的版面。

根據題目給定的資料範圍，第一跟第二步會超時。需要有某種方式去優化。

首先是第一步的檢查， 這步要檢查從 $(x,y)\sim(x+\text{stampHeight},y+\text{stampWidth})$ 的區塊總和是否為 $0$ ，
如果為 $0$ ，代表郵票可以安全的放上去。
那麼，有沒有一種方式能快速的找到「區塊總和」呢？
很明顯是用二維前綴和，這樣就能在 $O(mn)$ 計算好前綴和後，
而後續查找區塊總和只花 $O(1)$ 。

其次是第二步的放下郵票， 這步需要將 $(x,y)\sim(x+\text{stampHeight},y+\text{stampWidth})$ 的數值都增加一，
那麼，有沒有辦法快速將「一個區塊裡頭的數字」都增加一呢？
就是用前面提到的二維差分數組，能快速地將區塊的數值總和增加與減少。

程式碼

前綴和 + 差分數組

class Solution {
private:
    int getRegion(vector<vector<int>>& preSum, int x1, int y1, int x2, int y2) {
        return preSum[x2 + 1][y2 + 1] - preSum[x2 + 1][y1] - preSum[x1][y2 + 1] + preSum[x1][y1];
    }
    void add(vector<vector<int>>& diff, int x1, int y1, int x2, int y2) {
        x1++; y1++; x2++; y2++; // 改成 1-indexed 
        diff[x1][y1]++;
        diff[x1][y2 + 1]--;
        diff[x2 + 1][y1]--;
        diff[x2 + 1][y2 + 1]++;
    }
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> diff(m + 2, vector<int>(n + 2)); // 二維差分數組
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1)); // 二維前綴數組
        // 二維前綴數組初始化
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                preSum[i][j] = grid[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
            }
        }
        // 1. 檢查可以放郵票的區塊，枚舉左上角的座標
        // 2. 如果可以貼，就貼上去
        for(int i = 0; i <= m - stampHeight; i++) {
            for(int j = 0; j <= n - stampWidth; j++) {
                if(getRegion(preSum, i, j, i + stampHeight - 1, j + stampWidth - 1) == 0) { // 檢查區域面積
                    add(diff, i, j, i + stampHeight - 1, j + stampWidth - 1); // 貼上郵票
                }
            }
        }
        
        // 將二維差分數組做前綴和，轉換為正常版面的偏移量
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                grid[i - 1][j - 1] += diff[i][j]; // 把偏移量加到原先數組中
            }
        }
        
        // 3. 檢查貼完郵票之後的版面，可以跟上面的迴圈合併，這邊為了清晰，就不合了
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
};

複雜度分析

• 時間複雜度：$O(mn)$
• 空間複雜度：$O(mn)$