C++ BFS without hard-coded directions


  • 0
    Z
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.size() == 0) return;
    
        int rows = rooms.size(), cols = rooms[0].size();
        queue<pair<int, int>> bfs;
        
        // find all gates as starting points
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j) 
                if (rooms[i][j] == 0) bfs.push(make_pair(i, j));
        }
    
        while (!bfs.empty())
        {
            pair<int, int> pos = bfs.front(); bfs.pop();
            for (int i = max(0, pos.first - 1); i <= pos.first + 1 && i < rooms.size(); ++i)
            {
                for (int j = max(0, pos.second - 1); j <= pos.second + 1 && j < rooms[0].size(); ++j)
                {
                    // we only look at up, down, left and right cells
                    if ((i - pos.first) * (j - pos.second) == 0 && rooms[i][j] == INT_MAX)
                    {
                        rooms[i][j] = rooms[pos.first][pos.second] + 1;
                        bfs.push(make_pair(i, j));
                    }
                }
            }
        }
    }

Log in to reply
 

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