Use of bits to save space : O(m*n)


#1

vector<vector > Solution::queenAttack(vector &B) {
vector<vector >A(B.size(),vector(B[0].length(),0));
for(int i=0;i<B.size();i++)
{
for(int j=0;j<B[0].length();j++)
{
A[i][j]=B[i][j]-‘0’;
}
}
vector<vector >v (A.size(),vector(A[0].size(),0));
// int n=A.size(),m=A[0].size();
for(int i=0;i<A.size();i++)
{
for(int j=1;j<A[0].size();j++)
{
if(A[i][j-1]==1 || v[i][j-1])
{
v[i][j]=1;
// cout<<v[i][j]<<endl;
}
}
}

for(int i=0;i<A.size();i++)
{
    for(int j=A[0].size()-2;j>=0;j--)
    {
        if(A[i][j+1]==1 || ((v[i][j+1]>>1)&1))
        {
            v[i][j]=(v[i][j])|(1<<1);
        }
    }
}
for(int j=0;j<A[0].size();j++)
{
    for(int i=1;i<A.size();i++)
    {
        if(A[i-1][j]==1 || ((v[i-1][j]>>2)&1))
        {
            v[i][j]=(v[i][j])|(1<<2);
        }
    }
}
for(int j=0;j<A[0].size();j++)
{
    for(int i=A.size()-2;i>=0;i--)
    {
        if(A[i+1][j]==1 || ((v[i+1][j]>>3)&1))
        {
            v[i][j]=(v[i][j])|(1<<3);
        }
    }
}

for(int i=1;i<A.size();i++)
{
    for(int j=1;j<A[0].size();j++)
    {
        if(A[i-1][j-1]==1 || ((v[i-1][j-1]>>4)&1))
        {
            v[i][j]=(v[i][j]|(1<<4));
        }
    }
}
for(int i=1;i<A.size();i++)
{
    for(int j=A[0].size()-2;j>=0;j--)
    {
        if(A[i-1][j+1]==1 || ((v[i-1][j+1]>>5)&1))
        {
            v[i][j]=(v[i][j]|(1<<5));
        }
    }
}
for(int i=A.size()-2;i>=0;i--)
{
    for(int j=A[0].size()-2;j>=0;j--)
    {
        if(A[i+1][j+1]==1 || ((v[i+1][j+1]>>6)&1))
        {
            v[i][j]=(v[i][j]|(1<<6));
        }
    }
}
for(int i=A.size()-2;i>=0;i--)
{
    for(int j=1;j<A[0].size();j++)
    {
        if(A[i+1][j-1]==1 || ((v[i+1][j-1]>>7)&1))
        {
            v[i][j]=(v[i][j]|(1<<7));
        }
    }
}
for(int i=0;i<A.size();i++)
{
    for(int j=0;j<A[0].size();j++)
    {
        int c=0;
        for(int k=0;k<=7;k++)
        {
            c+=(v[i][j]>>k)&1;
        }
        v[i][j]=c;
    }
}
return v;

}