Non-DP solution


#1

typedef vector vi;
typedef vector vvi;

#define itoM (int i=0; i < M; ++i)
#define jtoN (int j=0; j < N; ++j)
#define ifromM (int i=M-1; i >= 0; --i)
#define jfromN (int j=N-1; j >= 0; --j)

vvi Solution::queenAttack(vector &A) {

const int M = A.size();
if (M==0) return {};
const int N = A[0].size();
if (N==0) return {};

vvi ans(M,vi(N,0));

bool haveq;

int ii; int jj;


for itoM {
    
    // rows left -> right
    haveq = false;
    for jtoN {
        ans[i][j] += haveq;
        if (A[i][j]=='1') haveq = true;
    }
    // rows right -> left
    haveq = false;
    for jfromN {
        ans[i][j] += haveq;
        if (A[i][j]=='1') haveq = true;
    }
    
}

for jtoN {
    
    // cols top -> bottom
    haveq = false;
    for itoM {
        ans[i][j] += haveq;
        if (A[i][j]=='1') haveq = true;
    }
    // cols bottom -> top
    haveq = false;
    for ifromM {
        ans[i][j] += haveq;
        if (A[i][j]=='1') haveq = true;
    }
    
}


for itoM {
    
    // diags tl -> br
    haveq = false;
    ii=i; jj=0;
    while(ii<M && jj<N) {
        ans[ii][jj] += haveq;
        if (A[ii][jj]=='1') haveq = true;
        ++ii; ++jj;
    }
    
    // diags br -> tl
    haveq = false;
    ii=i; jj=N-1;
    while(ii>=0 && jj>=0) {
        ans[ii][jj] += haveq;
        if (A[ii][jj]=='1') haveq = true;
        --ii; --jj;
    }
    
    // diags bl -> tr
    haveq = false;
    ii=i; jj=0;
    while(ii>=0 && jj<N) {
        ans[ii][jj] += haveq;
        if (A[ii][jj]=='1') haveq = true;
        --ii; ++jj;
    }
    
    // diags tr -> bl
    haveq = false;
    ii=i; jj=N-1;
    while(ii<M && jj>=0) {
        ans[ii][jj] += haveq;
        if (A[ii][jj]=='1') haveq = true;
        ++ii; --jj;
    }
    
}

for jtoN {
    
    
    // diags tl -> br
    if (j>0) {
        haveq = false;
        ii=0; jj=j;
        while(ii<M && jj<N) {
            ans[ii][jj] += haveq;
            if (A[ii][jj]=='1') haveq = true;
            ++ii; ++jj;
        }
    }
    
    
    if (j<(N-1)) {
        // diags br -> tl
        haveq = false;
        ii=M-1; jj=j;
        while(ii>=0 && jj>=0) {
            ans[ii][jj] += haveq;
            if (A[ii][jj]=='1') haveq = true;
            --ii; --jj;
        }
    }
    
    
    
    if (j>0) {
        // diags bl -> tr
        haveq = false;
        ii=M-1; jj=j;
        while(ii>=0 && jj<N) {
            ans[ii][jj] += haveq;
            if (A[ii][jj]=='1') haveq = true;
            --ii; ++jj;
        }
    }
    
    
    if (j<(N-1)) {
        // diags tr -> bl
        haveq = false;
        ii=0; jj=j;
        while(ii<M && jj>=0) {
            ans[ii][jj] += haveq;
            if (A[ii][jj]=='1') haveq = true;
            ++ii; --jj;
        }
    }
    
    
}

return ans;

}