C++ BFS solution O(m*n)


  • 0
    S

    Basic idea is push all 0's coordinates to the queue and set their distance[x][y] = 0 then we start BFS start from these points to update distance matrix:

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> res(m,vector<int>(n,0));
        if(matrix.empty()) return res;
        
        queue<pair<int,int>> q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j] ==0) q.push(make_pair(i,j));
                else                     res[i][j] = INT_MAX;
            }
        }
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(!q.empty())
        {
            int x= q.front().first;
            int y= q.front().second;
            q.pop();
            for(auto dir:dirs)
            {
                int xx = x+dir[0];
                int yy = y+dir[1];
                if(inrange(xx,yy,m,n) and res[xx][yy] > res[x][y]+1)
                {
                    res[xx][yy] = res[x][y]+1;
                    q.push(make_pair(xx,yy));
                }
            }
            
        }
        return res;
    }
    bool inrange(int x, int y, int m, int n)
    {
        if(x<0 or x>=m or y<0 or y>= n) return false;
        return true;
    }

Log in to reply
 

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