Clean C++ DFS Solution, 160ms beat 92% of submissions.


  • 0
    X
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            int x = rooms.size();
            if(x==0) return;
            int y = rooms[0].size();
            if(y==0) return;
            for(int i=0; i<x; i++){
                for(int j=0; j<y; j++){
                    if(rooms[i][j] == 0) walk(rooms, i, j, x, y);
                }
            }
        }
    private:
        void walk(vector<vector<int>>& rooms, int i, int j, int x, int y){
            int val = rooms[i][j];
            /*we check the value of it's neighbor, if the value is no bigger than the current value+1, 
            we don't have to go through this neighbor, because it will waste time and do nothing.*/
            if(i-1>=0 && rooms[i-1][j] > val+1){
                rooms[i-1][j] = val+1;
                walk(rooms, i-1, j, x, y);
            }
            if(j-1>=0 && rooms[i][j-1] > val+1){
                rooms[i][j-1] = val+1;
                walk(rooms, i, j-1, x, y);
            }
            if(i+1<x && rooms[i+1][j] > val+1){
                rooms[i+1][j] = val+1;
                walk(rooms, i+1, j, x, y);
            }
            if(j+1<y && rooms[i][j+1] > val+1){
                rooms[i][j+1] = val+1;
                walk(rooms, i, j+1, x, y);
            }
        }
    };

Log in to reply
 

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