Has anyone tried using BFS or DFS starting from empty room instead of gate


  • 0

    It always gets TLE, and for DFS solution, it is stackoverflow.
    I guess most testcases contain too many empty rooms compared to gates.


  • 0
    C

    Hi pinkfloyda, I tried this, but got a TLE.

    public class Solution {
    	 final int INF = 2147483647;
         boolean[][] visited;
        
        public void wallsAndGates(int[][] rooms) {
            if(rooms.length == 0) return;
            visited = new boolean[rooms.length][rooms[0].length];
            for(int i = 0; i < rooms.length; i++) {
                for(int j = 0; j < rooms[0].length; j++) {
                    if(rooms[i][j] == INF){
                    	visited = new boolean[rooms.length][rooms[0].length]; 
                        rooms[i][j] = getDistance(rooms, i, j, 0, rooms[i][j], visited);
                    }
                }
            }
        }
        
        private int getDistance(int[][] rooms, int i, int j, int distance, int shortest, boolean[][] visited) {
            int curShort = shortest;
            if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] == -1 || visited[i][j]) {
            	return INF;
            }
            visited[i][j] = true;
            if(rooms[i][j] == 0){
                return distance;
            }
    
            int result = Math.min(Math.min(getDistance(rooms, i+1, j, distance+1, shortest,visited),getDistance(rooms, i-1, j, distance+1, shortest,visited)),Math.min(getDistance(rooms, i, j+1, distance+1, shortest,visited),getDistance(rooms, i, j-1, distance+1, shortest,visited)));
            visited[i][j] = false;
            return result;
        }

  • 0

    Yes, your DFS solution will become stackoverflow, so I think for this question, we can only do DFS or BFS on Gates, there are much more empty rooms than gates.


  • 0
    C

    hmm.. is " there are much more empty rooms than gates" matters? Because I think it's possible that there are more gates than empty rooms. Right?


  • 0

    I cannot say for sure "much more empty rooms than gates" matters or not, I just feel it. For your case, if there are more gates, I think it should be easier for each DFS path reach that gate and return the function early without stackoverflow. And also I came out with the case, just imagine almost all cells are empty rooms except the right-bottom corner is the gate.


  • 0
    C

    Yes, you are right. I think another reason why start from gates is that each time when get an empty room, if the distance is smaller than the empty room's current distance, it can return. This is will decrease the number of calls.


  • 0
    S

    I have the same problem. Have you solved?


  • 0
    S

    finally I figured out the solution. We should prune the points that have been calculated before ---
    both in current recursion procedure and recursion procedure before.

    enter code here
    

    public class Solution {
    public final static int INF = 2147483647;

    public void wallsAndGates(int[][] rooms) {
       
        if(rooms == null || rooms.length == 0) return;
        
        int row = rooms.length;
        int col = rooms[0].length;
        
        boolean[][] visit = new boolean[row][col];
        
        for(int i = 0; i < rooms.length; i++){
            for(int j = 0; j < rooms[0].length; j++){
                //We only need to calculate the distance for points with value of INF
                if(rooms[i][j] == INF){
                    rooms[i][j] = dfs(i, j, rooms, visit);
                }
            }
        }
        
    }
    
    /
    //dfs will return the shortest distance from gate to current point(x, y)
    private int dfs(int x, int y, int[][] rooms, boolean[][] visit){
        int row = rooms.length;
        int col = rooms[0].length;
        
        //invalid point should not interrupt calculation for min, thus return INF
        if(x < 0 || x>= row || y < 0 || y >= col || rooms[x][y] == -1)
        return INF;
        
        
        //visited before(in current recursion procedure) 
        if(visit[x][y]) return rooms[x][y];
        
        visit[x][y] = true;
        
        if(rooms[x][y] == 0){
            return 0;
        } 
        
        //calculated before(not in current recursion procedure) 
        if(rooms[x][y] > 0 && rooms[x][y] < INF){
            return rooms[x][y];
        }
        
        
        int[] surroundx = new int[]{-1, 1, 0, 0};
        int[] surroundy = new int[]{0, 0, -1, 1};
        
        int min = rooms[x][y];
     
        for(int i = 0; i < 4; i++){
            int nextX = x + surroundx[i];
            int nextY =  y + surroundy[i];
    
            //min is the min distance among the surrounding 4 points to gates
            min = Math.min(min, dfs(nextX, nextY, rooms,  visit));
        }
        
        visit[x][y] = false;
        
        if(min == INF) return INF;
    
     //min is the min distance among the surrounding 4 points to gate, thus min distance of current point to gate is min + 1
        else return min + 1;
    }
    

    }


Log in to reply
 

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