Shortest solution using dfs on all 8 directions for every queen


#1
void dfs(vector<string> &A,vector<vector<int>> &dp,int i, int j, int xs, int ys) {
    if (i<0 or i>=A.size() or j<0 or j>=A[0].size()) return;
    dp[i][j]++;
    if (A[i][j]=='0') dfs(A,dp,i+xs,j+ys,xs,ys);
}

vector<vector<int> > Solution::queenAttack(vector<string> &A) {
    int n=A.size(),m=A[0].size();
    vector<vector<int>> dp(n,vector<int>(m,0));
    const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
    const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
    for (int i=0;i<n;++i) {
        for (int j=0;j<m;++j) {
            if (A[i][j]=='1') {
                for (int k=0;k<8;++k) {
                    dfs(A,dp,i+dx[k],j+dy[k],dx[k],dy[k]);
                }
            }
        }
    }
    return dp;
}

#2

What is the time complexity of this code? I don’t think this O(nm) and the editorial solution is also not O(nm). If I am wrong please tell me.


#3

i’m not sure about this but at max a cell in the end result can have a value of 8.
Which means each cell will be visited atmost 8 times.
Thus time complexity is O(8nm)