Iterative solution with O(n+m) space complexity


#1

vector<vector > Solution::queenAttack(vector &A) {
int n = A.size(), m = A[0].size();
// n*m
vector l(n,INT_MAX),r(n,INT_MIN);
vector t(m,INT_MAX),b(m,INT_MIN);
vector tr(m+n-1,INT_MAX),bl(m+n-1,INT_MIN); // 0 -> m+n-2
vector tl(m+n-1,INT_MAX),br(m+n-1,INT_MIN); // x-y -(m-1)-> (n-1)

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(A[i][j]=='1'){
            l[i] = min(l[i],j);
            r[i] = max(r[i],j);
            t[j] = min(t[j],i);
            b[j] = max(b[j],i);
            tr[i+j] = min(tr[i+j],i);
            bl[i+j] = max(bl[i+j],i);
            tl[i-j+(m-1)] = min(tl[i-j+(m-1)],i);
            br[i-j+(m-1)] = max(br[i-j+(m-1)],i);
        }
    }
}

vector<vector<int>> ans(n,vector<int>(m,0));
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        ans[i][j] += (l[i]!=INT_MAX&&l[i]<j)?(1):0;
        ans[i][j] += (r[i]!=INT_MIN&&r[i]>j)?(1):0;
        ans[i][j] += (t[j]!=INT_MAX&&t[j]<i)?(1):0;
        ans[i][j] += (b[j]!=INT_MIN&&b[j]>i)?(1):0;
        ans[i][j] += (tr[i+j]!=INT_MAX&&tr[i+j]<i)?(1):0;
        ans[i][j] += (bl[i+j]!=INT_MIN&&bl[i+j]>i)?(1):0;
        ans[i][j] += (tl[i-j+(m-1)]!=INT_MAX&&tl[i-j+(m-1)]<i)?(1):0;
        ans[i][j] += (br[i-j+(m-1)]!=INT_MIN&&br[i-j+(m-1)]>i)?(1):0;
    }
}

return ans;

}