Simple Solution for Queen Attack (using 8 direction Approach)


#1

int find(int Realx, int Realy, vector &A,int n, int m)
{
int X[8]={0,-1,-1,-1,0,1,1,1};
int Y[8]={1,1,0,-1,-1,-1,0,1};
int count=0;
for(int i=0;i<8;i++)
{
int x=Realx;
int y=Realy;
while(x<n && y<m && x>=0 && y>=0)
{
x+=X[i];
y+=Y[i];
if(x<n && y<m && x>=0 && y>=0 && A[x][y]==‘1’)
{
count++;
break;
}
}
}
return count;
}

vector<vector > Solution::queenAttack(vector &A) {

 int n=A.size();
 if(n==0)
   return {};
 int m=A[0].length();
 if(m==0)
   return {};
 vector<vector<int>> ans(n,vector<int>(m));
 for(int i=0;i<n;i++)
 {
     for(int j=0;j<m;j++)
     {
         ans[i][j]=find(i,j,A,n,m);
     }
 }
 return ans;

}


#2

for every {i,j} your find function runs.And each find function have asymptotic linear time complexity(let’s assume O(N)).Hence total time complexity of solution is O(nmN),but we are supposed to do in O(n*m)…correct me if i’m wrong.