生活随笔
收集整理的這篇文章主要介紹了
LeetCode 2132. 用邮票贴满网格图（DP/二维差分）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 題目
給你一個 m x n 的二進制矩陣 grid ，每個格子要么為 0 （空）要么為 1 （被占據）。
給你郵票的尺寸為 stampHeight x stampWidth 。我們想將郵票貼進二進制矩陣中，且滿足以下 限制 和 要求 ：
- 覆蓋所有 空 格子。
- 不覆蓋任何 被占據 的格子。
- 我們可以放入任意數目的郵票。
- 郵票可以相互有 重疊 部分。
- 郵票不允許 旋轉 。
- 郵票必須完全在矩陣 內 。
如果在滿足上述要求的前提下，可以放入郵票，請返回 true ，否則返回 false 。
示例 1：
輸入：grid
= [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]],
stampHeight
= 4, stampWidth
= 3
輸出：
true
解釋：我們放入兩個有重疊部分的郵票（圖中標號為
1 和
2），它們能覆蓋所有與空格子。
示例 2：
輸入：grid
= [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],
stampHeight
= 2, stampWidth
= 2
輸出：
false
解釋：沒辦法放入郵票覆蓋所有的空格子，且郵票不超出網格圖以外。提示：
m
== grid
.length
n
== grid
[r
].length
1 <= m
, n
<= 10^5
1 <= m
* n
<= 2 * 10^5
grid
[r
][c
] 要么是
0 ，要么是
1 。
1 <= stampHeight
, stampWidth
<= 10^5
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/stamping-the-grid
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- DP 的方法求矩形區域內的 1 的數量
- 如果 郵票區域內的 1 的數量為 0，則用差分方法（看的題解區做法）記錄這個區域訪問過（左上角、右下角+1，另外兩角 -1），再最后DP求差分的二維前綴和，前綴和為0則，該位置沒有被訪問過
class Solution {
public:bool possibleToStamp(vector
<vector
<int>>& grid
, int stampHeight
, int stampWidth
) {int m
= grid
.size(), n
= grid
[0].size();vector
<vector
<int>> dp(m
+1, vector
<int>(n
+1, 0));vector
<vector
<int>> diff(m
+2, vector
<int>(n
+2, 0));for(int i
= 0; i
< m
; ++i
){for(int j
= 0; j
< n
; ++j
){if(grid
[i
][j
])dp
[i
+1][j
+1] = 1+dp
[i
][j
+1]+dp
[i
+1][j
]-dp
[i
][j
];elsedp
[i
+1][j
+1] = dp
[i
][j
+1]+dp
[i
+1][j
]-dp
[i
][j
];}} for(int i
= 0; i
< m
; ++i
){for(int j
= 0; j
< n
; ++j
){if(grid
[i
][j
] || i
+stampHeight
> m
|| j
+stampWidth
> n
) continue;int outsidearea
= dp
[i
+stampHeight
][j
]+dp
[i
][j
+stampWidth
]-dp
[i
][j
];int allarea
= dp
[i
+stampHeight
][j
+stampWidth
];if(allarea
== outsidearea
) {diff
[i
+1][j
+1] += 1; diff
[i
+1][j
+stampWidth
+1] -= 1;diff
[i
+stampHeight
+1][j
+1] -= 1;diff
[i
+stampHeight
+1][j
+stampWidth
+1] += 1;}}}for(int i
= 0; i
< m
; ++i
){for(int j
= 0; j
< n
; ++j
){diff
[i
+1][j
+1] += diff
[i
+1][j
]+diff
[i
][j
+1]-diff
[i
][j
];if(grid
[i
][j
]==0 && diff
[i
+1][j
+1]==0) return false;}}return true;}
};
452 ms 178.5 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 2132. 用邮票贴满网格图（DP/二维差分）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
