C++ BFS solution based on queue


  • 0
    J

    In each turn, set all '1's we can reach to negative, which could be seen as "visited".

    class Solution {
    public:
    
        vector<int> dir = {0,1,0,-1,0};
    
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            // 1. initialize
            int m = matrix.size(), n = m ? matrix[0].size() : 0, steps = 1;
            queue<pair<int,int>> que;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j)
                    if(matrix[i][j] == 0) que.push({i,j});
            }
            
            // 2. BFS
            while(!que.empty()){
                int sz = que.size();
                while(sz-->0){
                    auto p = que.front();
                    que.pop();
                    for(int d = 0; d <4 ; ++d){
                        int x = p.first + dir[d], y = p.second + dir[d+1];
                        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= 0) continue; 
                        matrix[x][y] = -steps;
                        que.push({x,y});
                    }   
                }
                steps++;
            }
            
            // 3. reset values
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j)
                    if(matrix[i][j] < 0) matrix[i][j] = -matrix[i][j];
            }
            return matrix;
        }
    };
    

Log in to reply
 

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