01 Matrix

本文主要是介绍01 Matrix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Input:
[[0,0,0],[0,1,0],[1,1,1]]Output:
[[0,0,0],[0,1,0],[1,2,1]]

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

思路：这个思路比较巧妙的是，把0全部收集起来，然后从0开始往1里面走，往里面走，都是步子+1；

class Solution {public int[][] updateMatrix(int[][] mat) {if(mat == null || mat.length == 0 || mat[0].length == 0) {return mat;}int m = mat.length;int n = mat[0].length;Queue<int[]> queue = new LinkedList<>();boolean[][] visited = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(mat[i][j] == 0) {queue.offer(new int[]{i, j});visited[i][j] = true;}}}int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};while(!queue.isEmpty()) {int size = queue.size();for(int i = 0; i < size; i++) {int[] node = queue.poll();int x = node[0];int y = node[1];for(int[] dir: dirs) {int nx = x + dir[0];int ny = y + dir[1];if(0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny] && mat[nx][ny] == 1) {mat[nx][ny] = mat[x][y] + 1;visited[nx][ny] = true;queue.offer(new int[]{nx, ny});}}}}return mat;}
}

这篇关于01 Matrix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---