DFS Java solution 9ms


  • 0
    E

    Starts from 0 to do DFS. If existing step is not more than current one, stop DFS.

    public class Solution {
    public void wallsAndGates(int[][] rooms) {
    if (rooms == null || rooms.length == 0)
    return;

        for (int i = 0; i < rooms.length; i++){
        	for (int j = 0; j < rooms[0].length; j++){
        		if (rooms[i][j] == 0)
        		{
        			findAllReachableRooms(rooms, i, j, 0);
        		}
        	}
        }
        
        return;
    }
    
    private void findAllReachableRooms(int[][] rooms, int row, int col, int distance)
    {
    	if (rooms[row][col] > 0)
    	{
        	if (distance < rooms[row][col])
        		rooms[row][col] = distance;
        	else
        		return;
    	}
    	
    	if (row - 1 >= 0 && rooms[row-1][col] > 0)
    	{
    		findAllReachableRooms(rooms, row - 1, col, distance+1);
    	}
    	if (row + 1 < rooms.length && rooms[row+1][col] > 0)
    	{
    		findAllReachableRooms(rooms, row + 1, col, distance+1);
    	}
    	if (col - 1 >= 0 && rooms[row][col-1] > 0 )
    	{
    		findAllReachableRooms(rooms, row, col - 1, distance+1);
    	}
    	
    	if (col + 1 < rooms[0].length && rooms[row][col + 1] > 0)
    	{
    		findAllReachableRooms(rooms, row, col + 1, distance+1);
    	}
    }
    

    }


Log in to reply
 

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