My Java Solution with DFS / Flood Fill approach - Beats 79% Java Solutions!


  • 1
    G
    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            for(int i=0;i<rooms.length;i++){
                for(int j=0;j<rooms[0].length;j++){
                    if(rooms[i][j]==0){
                        inform(rooms,i,j,0);
                    }
                }
            }
        }
    
        private void inform(int[][] rooms,int i,int j,int dist){
            if(j>0 && rooms[i][j-1]>dist+1){
                rooms[i][j-1] = dist+1;
                inform(rooms,i,j-1,dist+1);
            }
            if(j<rooms[0].length-1 && rooms[i][j+1]>dist+1){
                rooms[i][j+1] = dist+1;
                inform(rooms,i,j+1,dist+1);
            }        
            if(i<rooms.length-1 && rooms[i+1][j]>dist+1){
                rooms[i+1][j] = dist+1;
                inform(rooms,i+1,j,dist+1);
            }
            if(i>0 && rooms[i-1][j]>dist+1){
                rooms[i-1][j] = dist+1;
                inform(rooms,i-1,j,dist+1);
            }        
        }
    }
    

  • 0
    C

    @ganesh9 I liked the idea to select '0' as starting point instead of empty room. This makes the solution much easier. cheers!


Log in to reply
 

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