LeetCode知识点总结 - 542

LeetCode 542. 01 Matrix考点难度ArrayMedium题目Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.The distance between two cells sharing a common edge is 1.思路Initialize queue with ALL 0 cells, mark 1 cells as -1 (unvisited)Multi-source BFS: For each cell processed, check its 4 neighbors. If a neighbor is unvisited (-1), set its distance current cell distance 1 and add it to the queue答案classSolution{int[]DIRnewint[]{0,1,0,-1,0};publicint[][]updateMatrix(int[][]mat){intmmat.length,nmat[0].length;// The distance of cells is up to (MN)Queueint[]qnewArrayDeque();for(intr0;rm;r)for(intc0;cn;c)if(mat[r][c]0)q.offer(newint[]{r,c});elsemat[r][c]-1;// Marked as not processed yet!while(!q.isEmpty()){int[]currq.poll();intrcurr[0],ccurr[1];for(inti0;i4;i){intnrrDIR[i],nccDIR[i1];if(nr0||nrm||nc0||ncn||mat[nr][nc]!-1)continue;mat[nr][nc]mat[r][c]1;q.offer(newint[]{nr,nc});}}returnmat;}}