01 Matrix
给一个0和1矩阵, 问其中每个1距离0的距离. 先记录一下0的位置, 然后把1的位置set成最大值, 遍历每个0的位置,然后对每个相邻的值做比较. 如果小, 就取小的.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public int[][] updateMatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; Queue<int[]> q = new LinkedList<>(); for(int i = 0 ; i < m ; i++) { for(int j = 0 ; j < n; j++) { if(matrix[i][j] == 0) q.add(new int[]{i,j}); else matrix[i][j] = Integer.MAX_VALUE; // set the distance to max } } int[][] dirs = { {-1,0}, {1,0}, {0,1}, {0,-1} }; while(!q.isEmpty()) { int[] cell = q.poll(); for(int[] d : dirs) { int r = cell[0] + d[0]; int c = cell[1] + d[1]; if(0 <= r && r < m && 0 <= c && c < n && matrix[cell[0]][cell[1]] < matrix[r][c]) { q.add(new int[]{r,c}); matrix[r][c] = matrix[cell[0]][cell[1]] + 1; } } } return matrix; } } |