Easy C++ BFS Solution


  • 0
    M
        vector<vector<int>> dir={{-1,0}, {1,0}, {0,-1}, {0,1}};
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<int> r, next;
            queue<vector<int>> q;
            for(int i=0;i<matrix.size();i++) {
                for(int j=0;j<matrix[0].size();j++) {
                    if(matrix[i][j]==0) {
                        r={i, j};
                        q.push(r);
                    }
                    if(matrix[i][j]==1) matrix[i][j]=INT_MAX;
                }
            }
            while(!q.empty()) {
                for(int i=0;i<4;i++) {
                    r=q.front();
                    next=r;
                    next[0]+=dir[i][0], next[1]+=dir[i][1]; 
                    if(next[0]>=matrix.size()||next[0]<0||next[1]>=matrix[0].size()||next[1]<0) continue;
                    if(matrix[next[0]][next[1]]==INT_MAX) {
                        matrix[next[0]][next[1]]=matrix[r[0]][r[1]]+1;
                        q.push(next);
                    }
                }
                q.pop();
            }
            return matrix;
        }

Log in to reply
 

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