*Java* DFS solution (8ms beats 80%)


  • 0
    E
    private static final int INF = 0x7fffffff;
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;
    	if(m == 0) return;
        int n = rooms[0].length;
        
        int[][] dirs = {{-1,0}, {1,0}, {0,1}, {0,-1}};
        for(int i=0; i<m; i++) {
        	for(int j=0; j<n; j++) {
        		if(rooms[i][j]==0) dfs(rooms, dirs, m, n, i, j, 0, INF);
        	}
        }
    }
    
    private void dfs(int[][] rooms, int[][] dirs, int rows, int cols, int i, int j, int distance, int INF) {
    	for(int[] dir : dirs) {
    		int ii = i+dir[0], jj = j+dir[1];
    		if(ii>=0 && ii<rows && jj>=0 && jj<cols 
    				&& rooms[ii][jj]>0 && distance+1 < rooms[ii][jj]) {
    			rooms[ii][jj] = distance + 1;
    			dfs(rooms, dirs, rows, cols, ii, jj, distance+1, INF);
    		}
    	}
    }

  • 0
    D

    I think it's better to call your solution DFS.


  • 0
    E

    You are right, it is DFS. Thanks for pointing it out.


Log in to reply
 

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