Solution with O(N) additional memory. (Since my vector<vector<vector<int>>> dp with M*N*8 failed with MLE :/)


#1

struct DPCache
{
DPCache(int size) : m_row(1)
{
dp = vector<vector<vector>>(2, vector<vector>(size, vector(9, 0)));
}
int getValue(int i, int j, int k)
{
return dp[(m_row+i+2)%2][j][k];
}

int setValue(int i, int j, int k, int val)
{
    dp[(m_row+i+2)%2][j][k] = val;
}

void commitRow()
{
    // cout << "Prev Row:"  << endl;
    // for(int k=0; k<9; ++k)
    // {
    //     for(int i=0; i<dp[m_row].size(); ++i) cout << dp[m_row][i][k] << " ";
    //     cout << endl;
    // }
    // cout << endl;
    m_row++;
    m_row %= 2;
}

private:
int m_row;
vector<vector<vector>> dp;
};

vector<vector > Solution::queenAttack(vector &A) {
DPCache dp1(A[0].size());
DPCache dp2(A[0].size());
vector<vector> sol(A.size(), vector(A[0].size(), 0));
for(int i=0; i<A.size(); ++i)
{
for(int j=0; j<A[i].size(); ++j)
{
for(int k=0; k<9; ++k)
{
//cout << i << " " << j << " " << k << endl;
int refI = i;
int refJ = j;
DPCache *refDP = &dp1;
if(k==4) continue;
if(k>=5)
{
refDP = &dp2;
refI = A.size()-i-1;
refJ = A[i].size()-j-1;
}
int rd = - 1 + (k/3);
int cd = -1 + (k%3);
if(refI+rd<0 || refJ+cd<0 || refI+rd >= A.size() || refJ+cd >= A[i].size())
refDP->setValue(0, refJ, k, 0); //dp[refI][refJ][k] = 0;
else if(A[refI+rd][refJ+cd]==‘1’)
refDP->setValue(0, refJ, k, 1); //dp[refI][refJ][k] += 1;
else
refDP->setValue(0, refJ, k, refDP->getValue(rd, refJ+cd, k)); //dp[refI][refJ][k] = dp[rd][cd][k];

            sol[refI][refJ] += refDP->getValue(0, refJ, k);
        }
        // cout << "SOL:" << endl;
        // for(int i=0; i<A.size(); ++i)
        // {
        //     for(int j=0; j<A[0].size(); ++j)
        //     {
        //         cout << sol[i][j] << " ";
        //     }
        //     cout << endl;
    }
    //cout << "DP1" << endl;
    dp1.commitRow();
    //cout << "DP2" << endl;
    dp2.commitRow();
}
return sol;

}


#2

No it does not . Depends on your implementation . Following is my accepted code with NM8 memory

#include<bits/stdc++.h>
vector<vector<int> > Solution::queenAttack(vector<string> &A) {
    vector<vector<vector<int>>> dp(A.size(),vector<vector<int>>(A[0].size(),vector<int>(8,0)));
    for(int i=0;i<A.size();i++){
        for(int j=0;j<A[0].size();j++){
            if(i)
            dp[i][j][2]=dp[i][j][2]||dp[i-1][j][2]||(A[i-1][j]=='1');
            if(j)
            dp[i][j][0]=dp[i][j][0]||dp[i][j-1][0]||(A[i][j-1]=='1');
            if(j!=A[0].size()-1)
            dp[i][j][4]=dp[i][j][4]||dp[i][j+1][4]||(A[i][j+1]=='1');
            if(i!=A.size()-1)
            dp[i][j][6]=dp[i][j][6]||dp[i+1][j][6]||(A[i+1][j]=='1');
            if(i&&j)
            dp[i][j][1]=dp[i][j][1]||dp[i-1][j-1][1]||(A[i-1][j-1]=='1');
            if(i&&j!=A[0].size()-1)
            dp[i][j][3]=dp[i][j][3]||dp[i-1][j+1][3]||(A[i-1][j+1]=='1');
            if(i!=A.size()-1&&j!=A[0].size()-1)
            dp[i][j][5]=dp[i][j][5]||dp[i+1][j+1][5]||(A[i+1][j+1]=='1');
            if(i!=A.size()-1&&j)
            dp[i][j][7]=dp[i][j][7]||dp[i+1][j-1][7]||(A[i+1][j-1]=='1');
        }
    }
    for(int i=A.size()-1;i>=0;i--){
        for(int j=A[0].size()-1;j>=0;j--){
            if(i)
            dp[i][j][2]=dp[i][j][2]||dp[i-1][j][2]||(A[i-1][j]=='1');
            if(j)
            dp[i][j][0]=dp[i][j][0]||dp[i][j-1][0]||(A[i][j-1]=='1');
            if(j!=A[0].size()-1)
            dp[i][j][4]=dp[i][j][4]||dp[i][j+1][4]||(A[i][j+1]=='1');
            if(i!=A.size()-1)
            dp[i][j][6]=dp[i][j][6]||dp[i+1][j][6]||(A[i+1][j]=='1');
            if(i&&j)
            dp[i][j][1]=dp[i][j][1]||dp[i-1][j-1][1]||(A[i-1][j-1]=='1');
            if(i&&j!=A[0].size()-1)
            dp[i][j][3]=dp[i][j][3]||dp[i-1][j+1][3]||(A[i-1][j+1]=='1');
            if(i!=A.size()-1&&j!=A[0].size()-1)
            dp[i][j][5]=dp[i][j][5]||dp[i+1][j+1][5]||(A[i+1][j+1]=='1');
            if(i!=A.size()-1&&j)
            dp[i][j][7]=dp[i][j][7]||dp[i+1][j-1][7]||(A[i+1][j-1]=='1');
        }
    }
    vector<vector<int>> ans(A.size(),vector<int>(A[0].size(),0));
    for(int i=0;i<A.size();i++){
        for(int j=0;j<A[0].size();j++)
        ans[i][j]=accumulate(dp[i][j].begin(),dp[i][j].end(),0);
    }
    return ans;
}