Java easy understand BFS solution


  • 0
    F
    public int[][] updateMatrix(int[][] matrix) {
    	if (matrix == null || matrix.length == 0)
    		return matrix;
    
    	int n = matrix.length;
    	int m = matrix[0].length;
    
    	Queue<int[]> queue = new LinkedList<>();
    	int[][] res = new int[n][m];
    
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (matrix[i][j] == 0) {
    				queue.add(new int[] { i, j });
    			}
    		}
    	}
    
    	int[][] dir = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
    	while (!queue.isEmpty()) {
    		int len = queue.size();
    		for (int k = 0; k < len; k++) {
    			int[] node = queue.poll();
    			int i = node[0];
    			int j = node[1];
    			for (int[] d : dir) {
    				int x = node[0] + d[0];
    				int y = node[1] + d[1];
    				if (x >= 0 && x < n && y >= 0 && y < m
    						&& matrix[x][y] == 1) {
    					if (res[x][y] == 0) {
    						queue.add(new int[] { x, y });
    						res[x][y] = res[i][j] + 1;
    					} else {
    						res[x][y] = Math.min(res[x][y], res[i][j] + 1);
    					}
    				}
    			}
    
    		}
    	}
    	return res;
    }

Log in to reply
 

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