本文主要是介绍力扣2132.用邮票贴满网格图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣2132.用邮票贴满网格图
-
二维差分 + 二维前缀和
- 对于一个可以贴邮票的矩阵，其和一定为0
- 通过前缀和可以求出任意一个矩阵的和，为0时贴上邮票
- 贴上邮票即为在矩阵+1，可以用二维差分实现
- 最后差分求和，若一个格子grid[i][j] == 0 && sum == 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>> s(m+1,vector<int>(n+1));for(int i=0;i<m;i++)for(int j=0;j<n;j++)s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + grid[i][j];//求差分数组vector<vector<int>> d(m+2,vector<int>(n+2));for(int i2=stampHeight;i2<=m;i2++){for(int j2=stampWidth;j2<=n;j2++){//左上角坐标int i1 = i2 - stampHeight + 1;int j1 = j2 - stampWidth + 1;//这个矩阵全为0，可以贴邮票if(s[i2][j2] - s[i2][j1-1] - s[i1-1][j2] + s[i1-1][j1-1] == 0){d[i1][j1] ++;d[i1][j2+1] --;d[i2+1][j1] --;d[i2+1][j2+1] ++;}}}//复原差分数组for(int i=0;i<m;i++)for(int j=0;j<n;j++){d[i+1][j+1] += d[i+1][j] + d[i][j+1] - d[i][j];//应该贴但是没贴if(grid[i][j] == 0 && d[i+1][j+1] == 0)return false;}return true;}};
这篇关于力扣2132.用邮票贴满网格图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
