clean C++ code with 0(N) time complexity


  • 0
    class Solution {
      public:
    struct node
    {
        int x,y;
    };
    int f[4][2]={0,1,0,-1,1,0,-1,0};
    
    vector<vector<int> > updateMatrix(vector<vector<int>>& matrix) 
    {
        vector<vector<int> > ans=matrix;
        
        int n=matrix.size();
        int m=matrix[0].size();
        
        for(int i=0;i<n;i++)
         for(int j=0;j<m;j++)
                 ans[i][j]=100000;
        queue<node> myq;
    
        for(int i=0;i<n;i++)
         for(int j=0;j<m;j++)
         {
             if(matrix[i][j]==0)
             {
                 node tmp;
                 tmp.x=i;
                 tmp.y=j;
                 myq.push(tmp);
                 ans[i][j]=0;
             }
         }
         
         while(!myq.empty())
         {
             node cur=myq.front();
             myq.pop();
             for(int i=0;i<4;i++)    //travel 4 directions
             {
                 node next=cur;
                 next.x+=f[i][0];
                 next.y+=f[i][1];
                 if(next.x>=0&&next.y>=0&&next.x<n&&next.y<m&&ans[cur.x][cur.y]+1<ans[next.x][next.y])
                 {
                     ans[next.x][next.y]=ans[cur.x][cur.y]+1;
                     myq.push(next);
                 }
                 
             }
         }
      
         return ans;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.