C++ O(mn) BFS with #define helper


  • 2

    Level-by-level BFS, maybe two or three somewhat interesting bits (the initialization of n, the d+k loops, and the define).

    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size(), n = m ? rooms[0].size() : 0;
        queue<pair<int,int>> q;
        for (int i=0; i<m; ++i)
            for (int j=0; j<n; ++j)
                if (!rooms[i][j])
                    q.push({i, j});
        for (int d=1; q.size(); ++d) {
            for (int k=q.size(); k--; ) {
                int i = q.front().first, j = q.front().second;
                q.pop();
                #define add(in, i, j) if (in && rooms[i][j] > d) { q.push({i, j}); rooms[i][j] = d; }
                add(i, i-1, j);
                add(i+1<m, i+1, j);
                add(j, i, j-1);
                add(j+1<n, i, j+1);
                #undef add
            }
        }
    }

  • 0

    Haha, you define a nice #define instead of using a function. Very inspiring :-)


  • 0

    I try to replace your #define with a private function and I find that the function needs too many parameters :-)

    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            int m = rooms.size(), n = m ? rooms[0].size() : 0;
            queue<pair<int, int>> q;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (!rooms[i][j]) q.push({i, j});
            for (int d = 1; !q.empty(); d++) {
                for (int k = q.size(); k; k--) {
                    int i = q.front().first, j = q.front().second;
                    q.pop();
                    add(rooms, q, i - 1, j, m, n, d);
                    add(rooms, q, i + 1, j, m, n, d);
                    add(rooms, q, i, j - 1, m, n, d);
                    add(rooms, q, i, j + 1, m, n, d); 
                }
            }
        }
    private:
        void add(vector<vector<int>>& rooms, queue<pair<int, int>>& q, int i, int j, int m, int n, int d) {
            if (i >= 0 && i < m && j >= 0 && j < n && rooms[i][j] > d) {
                q.push({i, j});
                rooms[i][j] = d;
            }
        }
    };

  • 0

    Well, you also changed it. In my version, each of the four calls only does the one boundary check it needs to do. If you do that as well, then your function doesn't need m and n. But yeah, still a lot of overhead.

    Oh, I just remembered C++ has lambdas now. You wanna try that?


  • 0

    Oh, C++ lambda, still haven't used it before...


  • 0
    J

    If I understand correct, d = rooms[i][j] + 1
    If that is the case,the last 2 for-loop can be replace as
    while(!q.empty())
    {
    int i = q.front().first, j = q.front().second;
    int d = room[i][j] + 1;
    ...
    }


Log in to reply
 

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