Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

Given a matrix mat consisting of 0 and 1, output a matrix of the same size, where each cell is the distance from the element at the corresponding position in MAT to the nearest 0.

The distance between two adjacent elements is 1.

Example 1:

Input: mat = [[0, 0], [0, 0], [0, 0]] output: [[0, 0], [0, 0], [0, 0]] example 2:

Input: mat = [[0, 0], [0, 0], [1,1,1]] output: [[0, 0], [0, 0], [1, 2, 1]]

Tip:

M == mat.length n == mat.length 1 <= m, n <= 104 1 <= m * n <= 104 mat[I][j] is either 0 or 1

Source: LeetCode link: leetcode-cn.com/problems/01…

Ii. Analysis of Ideas:

In this case, a scenario is given: find the distance between the element at the corresponding position in MAT and the nearest 0. It’s the number of steps you can take to get to another point. The easiest way to find the shortest distance from one point is to think of degree-first traversal, which is to search one circle around you, and then search the next circle, slowly expanding the search area.

Specific practices:

First, the coordinates of all elements 0 in the matrix are added to the queue, and the element is taken out from the head of the queue and diffused from the current node, under the condition that the diffused is within the range of the matrix and has not been accessed.

We also need to know the coordinates of the position to be changed first. It must be the first point of arrival, that is, the nearest point. We set this position to true so that when others arrive at this position slowly in the future, they cannot change the value of this position

Iii. AC Code:

Class Solution {int[] dx=new int[]{0,1,0,-1}; Int [] dy = new int [] {1, 0, 1, 0}; public int[][] updateMatrix(int[][] mat) { int m=mat.length; int n=mat[0].length; Queue<int[]> q=new LinkedList<>(); boolean[][] flag=new boolean[m][n]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(mat[i][j]==0){ q.offer(new int[]{i,j}); flag[i][j]=true; } } } while(! q.isEmpty()){ int[] temp=q.poll(); for(int t=0; t<4; t++){ int x=temp[0]+dx[t]; int y=temp[1]+dy[t]; if(x>=0&&x<m&&y>=0&&y<n&&mat[x][y]==1&&! flag[x][y]){ q.offer(new int[]{x,y}); mat[x][y]=mat[temp[0]][temp[1]]+1; flag[x][y]=true; } } } return mat; }}Copy the code

Iv. Summary:

Because you want the nearest, you usually want to use BFS, and if you want the farthest, you usually want to use DFS.

Deep traversal template ideas: the first step: clear recursive parameters; the second step: clear recursive termination conditions; the third step: clear the contents of the recursive function; the fourth step: clear backtracking return values

Step 1: set the queue and add the initial node step 2: judge whether the queue is empty Step 3: iterate to eject the queue element and logically process the subordinate element of the current queue element. Step 4: Perform step 3 here

Writing questions is not easy, if it helps you, click “like” and leave. Remember, (゚▽゚) Blue, if there is an insufficiency, please do.