176ms DFS(backtracking) solution


  • 1
    W

    I think the worst case time complicity for this is much more than BFS, O((MN)^2) in worst case. Please let me know if this is correct.

    Let the code tell:

    class Solution {
    public:
        using Rooms = vector<vector<int>>;
        void wallsAndGates(Rooms& rooms) {
            if (rooms.empty() || rooms.back().empty()) return;
            for (int i = 0; i < rooms.size(); ++i) {
                for (int j = 0; j < rooms[i].size(); ++j) {
                    if (rooms[i][j] == 0) {
                        traverse(rooms, i, j, 0);
                    }
                }
            }
        }
        
        void traverse(Rooms& rooms, const int i, const int j, const int comparer) {
            if (i < 0 || j < 0 || i >= rooms.size() || j >= rooms[i].size() || rooms[i][j] == -1) return;
            if (comparer <= rooms[i][j]) {
                rooms[i][j] = comparer;
                traverse(rooms, i + 1, j, comparer + 1);
                traverse(rooms, i - 1, j, comparer + 1);
                traverse(rooms, i, j + 1, comparer + 1);
                traverse(rooms, i, j - 1, comparer + 1);
            }
        }
    };

  • 0
    D

    Shouldn't you end up in a forever cycle. Since you aren't keeping track of whether you visited a particular cell of matrix. So you can keep on going to and fro. Just curious.


  • 0
    W

    Hi debseal, that's a great concern, however, since I changed the value of matrix I visited everytime and only enter another DFS if the comparer is less than the value of the room, so there won't be any forever loop in my code.
    Please let me know if you understand this.


  • 0
    D

    Hi Yang,
    My bad, should have looked into the code in greater detail. Make sense.


Log in to reply
 

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