C++ dfs solution got tle


  • 0
    Q
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            if(rooms.empty() || rooms[0].empty())
                return;
            int len1 = rooms.size(), len2 = rooms[0].size();
            int layer = 1;
            vector<vector<bool>> visited(len1,vector<bool>(len2,false));
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    if(rooms[i][j] == 0)
                        dfs(rooms,i,j,layer,visited);
                }
            }
            return;
        }
        
        void dfs(vector<vector<int>>& rooms,int i, int j,int layer, vector<vector<bool>> &visited){
            int len1 = rooms.size(), len2 = rooms[0].size();
            
            vector<pair<int,int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for(auto it:dir){
                int idx = i+it.first, idy = j+it.second;
                //cout<<"line 25 "<<idx<<" "<<idy<<endl;
                if(!check(len1,len2,idx,idy,rooms,visited))
                    continue;
                if(rooms[idx][idy] <= layer)
                    continue;
                
                rooms[idx][idy] = layer;
                visited[idx][idy] = true;
                dfs(rooms,idx,idy,layer+1,visited);
                visited[idx][idy] = false;
            }
            return;
        }
        
        bool check(int len1, int len2, int i, int j, vector<vector<int>> rooms, vector<vector<bool>> &visited){
            if(i<0 || j<0 || i>=len1 || j>=len2 || rooms[i][j] == -1 || visited[i][j] == true)
                return false;
            else
                return true;
        }
    };
    

Log in to reply
 

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