C++ BFS Simple Solution


  • 0

    Inspired by @lchen77 's solution on reducing time complexity

    class Solution {
    public:
        void bfs(vector<vector<int>>& rooms, int x, int y) {
            int m = rooms.size(), n = rooms[0].size();
            vector<pair<int, int>> nei = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            queue<pair<int, int>> qu;
            qu.push({x, y});
            while (qu.size()) {
                int r = qu.front().first, c = qu.front().second;
                qu.pop();
                for (auto i : nei) {
                    int rr = r + i.first, cc = c + i.second;
                    if (rr >= 0 && rr < m && cc >= 0 && cc < n && rooms[rr][cc] > rooms[r][c] + 1) {
                        rooms[rr][cc] = rooms[r][c] + 1;
                        qu.push({rr, cc});
                    }
                }
            }
        }
        void wallsAndGates(vector<vector<int>>& rooms) {
            int m = rooms.size(), n = m ? rooms[0].size() : 0;
            if (!m)
                return;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (rooms[i][j] == 0)
                        bfs(rooms, i, j);
        }
    };
    

Log in to reply
 

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