O(mn) solution with dp


#1

vector<vector > Solution::queenAttack(vector &A) {
int n=A.size();
int m=A[0].size();
int a[4]={0,-1,-1,-1};
int b[4]={-1,-1,0,1};
vector<vector<vector>>dp1(n,vector<vector>(m,vector(4,0)));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<4;k++)
{
int x=i+a[k];
int y=j+b[k];
if(x<0 || y<0 || x>=n || y>=m)
continue;
dp1[i][j][k]=((dp1[x][y][k]&1) | (A[x][y]&1));
}
}
}
int f[4]={0,1,1,1};
int g[4]={1,1,0,-1};
vector<vector<vector>>dp2(n,vector<vector>(m,vector(4,0)));
for(int i=n-1;i>=0;i–)
{
for(int j=m-1;j>=0;j–)
{
for(int k=0;k<4;k++)
{
int x=i+f[k];
int y=j+g[k];
if(x<0 || y<0 || x>=n || y>=m){
continue;
}
dp2[i][j][k]=((dp2[x][y][k]&1) | (A[x][y]&1));
}
}
}
vector<vector>dp3(n,vector(m,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int sum=0;
for(int k=0;k<4;k++)
{
sum=sum+dp1[i][j][k]+dp2[i][j][k];
}
dp3[i][j]=sum;
}
}
return dp3;
}