The title

Multi-source BFS

Public int[] updateMatrix(int[][] matrix) {distance[I][j] represents the minimum distance to 0 int[][] distance = new int[matrix.length][matrix[0].length]; boolean [][] visited = new boolean[matrix.length][matrix[0].length]; Queue<int []> queue = new LinkedList(); for (int i = 0; i < matrix.length; i ++) { for (int j = 0; j < matrix[0].length; j ++) { if (matrix[i][j] == 0) { queue.offer(new int[]{i, j}); distance[i][j] = 0; visited[i][j] = Boolean.TRUE; } } } int [] temp1 = new int[] {0, 0, 1, -1}; int [] temp2 = new int[] {1, -1, 0, 0}; while (! queue.isEmpty()) { int size = queue.size(); // For (int I = 0; int I = 0; i < size; i ++) { int [] origin = queue.poll(); for (int j = 0; j < 4; j ++) { int targetRow = origin[0] + temp1[j]; int targetCol = origin[1] + temp2[j]; if (targetRow >=0 && targetRow < matrix.length && targetCol >= 0 && targetCol < matrix[0].length && ! visited[targetRow][targetCol]) { distance[targetRow][targetCol] = distance[origin[0]][origin[1]] + 1; visited[targetRow][targetCol] = Boolean.TRUE; queue.offer(new int[] {targetRow, targetCol}); } } } } return distance; }Copy the code

Train of thought

(1) the purpose is to find the distance of 1 to 0 recently, suppose we 1 as the starting point, through the up and down or so four directions to look for, and then the next round will involve four nodes are added to the queue, as the starting point for the next round, and then the next round for each starting point, and once again spread up and down or so, only to hit the first 0, the spread of the wheel, It’s distance.

But in this case, I have to start with 1 and spread it out, and there’s a lot of double counting that I can’t use, like a lot of distance from 1 to 1, what does that help us? And the distance from 1 to 1 itself, it doesn’t matter, you can only calculate the distance by the number of rounds

(2) but if our starting point is zero, looking for 1, according to the question the zero distance is 1 0, 0 in diffusion once, each position (except to itself is 0) distance from the current zero distance can be calculated, and the distance in a diffusion can be used, the results can be recorded, no double counting. If there’s only one zero, then this idea is enough.

(3) If there are more than one 0, it becomes a problem which 0 spreads first. Therefore, we can treat all 0’s as the same 0 and let everyone spread together. In this way, we can guarantee that the 0 that every non-0 element is diffused to must be one of the nearest 0’s. Because if you have a 1 that has 0’s on both sides, even though the 0’s actually spread out one after the other, but in the case of just one step, being spread out by the 0’s on the left is the same thing as being spread out by the 0’s on the right.

By spreading simultaneously, you don’t have to have a minimum distance, because that’s the minimum distance that can be spread