二维前缀和+二维差分

原题链接

二维前缀和
pre[i][j]=pre[i-1][j]+pre[i][j-1]+a[i][j]-pre[i-1][j-1]

一维差分要修改2个位置即(l->r)
p[l]+=x
p[r+1]-=x

二维差分要修改4个位置即(i,j)->(x,y)
p[i][j]+=x
p[x+1][j]-=x
p[i][y+1]-=x
p[x+1][y+1]+=x

#include 
using namespace std;
int n,m;
class Solution {
public:bool possibleToStamp(vector<vector<int>>& vee, int a, int b) {n=vee.size();m=vee[0].size();int v[n+2][m+2];int cp[n+2][m+2];int pre[n+2][m+2];int sum[n+2][m+2];memset(v,0,sizeof(v));memset(pre,0,sizeof(pre));memset(cp,0,sizeof(cp));memset(sum,0,sizeof(sum));for(int i=0;i<n;i++){for(int j=0;j<m;j++){v[i+1][j+1]=vee[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+v[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int nx=i+a-1;int ny=j+b-1;if(nx>n||ny>m){continue;}int uu=pre[nx][ny]-pre[nx-a][ny]-pre[nx][ny-b]+pre[nx-a][ny-b];if(uu==0){cp[i][j]+=1;cp[nx+1][j]+=-1;cp[i][ny+1]+=-1;cp[nx+1][ny+1]+=1;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+cp[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){v[i][j]+=sum[i][j];if(v[i][j]==0){return false;}}}return true;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！