阅读量:0
class Solution { public: int numberOfSubmatrices(vector<vector<char>>& grid) { int n=grid.size(); int m=grid[0].size(); vector<vector<int>> prex(n+1,vector<int>(m+1,0)); vector<vector<int>> prey(n+1,vector<int>(m+1,0)); for(int i=1;i<n+1;i++){ for(int j=1;j<m+1;j++){ if(grid[i-1][j-1]=='X'){ prex[i][j]=prex[i-1][j]+prex[i][j-1]-prex[i-1][j-1]+1;} else{ prex[i][j]=prex[i-1][j]+prex[i][j-1]-prex[i-1][j-1]+0; } if(grid[i-1][j-1]=='Y'){ prey[i][j]=prey[i-1][j]+prey[i][j-1]-prey[i-1][j-1]+1; }else{ prey[i][j]=prey[i-1][j]+prey[i][j-1]-prey[i-1][j-1]+0; } } } int res=0; for(int i=1;i<n+1;i++){ for(int j=1;j<m+1;j++){ int countx=prex[i][j]-prex[0][j]-prex[i][0]+prex[0][0]; int county=prey[i][j]-prey[0][j]-prey[i][0]+prey[0][0]; if(countx==county && countx>0){res++;} } } return res; } };二维前缀和 前缀和数组定义时扩宽一层
