项目作者: eMahtab

项目描述 :
01 Matrix
高级语言:
项目地址: git://github.com/eMahtab/01-matrix.git
创建时间: 2020-02-22T04:00:46Z
项目社区:https://github.com/eMahtab/01-matrix

开源协议:

下载


01-matrix

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.

  1. Example 1:
  2. Input:
  3. [[0,0,0],
  4. [0,1,0],
  5. [0,0,0]]
  6. Output:
  7. [[0,0,0],
  8. [0,1,0],
  9. [0,0,0]]
  10. Example 2:
  11. Input:
  12. [[0,0,0],
  13. [0,1,0],
  14. [1,1,1]]
  15. Output:
  16. [[0,0,0],
  17. [0,1,0],
  18. [1,2,1]]

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

Approach :

We can’t solve this problem in one pass through the matrix, as it will lead to wrong result.

  1. e.g.
  2. {0, 1, 1, 1},
  3. {1, 1, 1, 1},
  4. {1, 1, 1, 1},
  5. {1, 1, 1, 0}

If we just see the four adjacent cells of a cell to determine the result in one pass, it will lead to wrong result for the above matrix. Correct answer will be :

  1. {0, 1, 2, 3},
  2. {1, 2, 3, 2},
  3. {2, 3, 2, 1},
  4. {3, 2, 1, 0}

Implementation 1 : BFS Approach

  1. class Solution {
  2. private class Position {
  3. int row, column;
  4. Position(int row, int column) {
  5. this.row = row;
  6. this.column = column;
  7. }
  8. }
  9. public int[][] updateMatrix(int[][] matrix) {
  10. if(matrix == null || matrix.length == 0)
  11. return matrix;
  12. int rows = matrix.length;
  13. int cols = matrix[0].length;
  14. Queue<Position> q = new LinkedList<>();
  15. for(int i = 0; i < rows; i++) {
  16. for(int j = 0; j < cols; j++) {
  17. if(matrix[i][j] == 0)
  18. q.add(new Position(i, j));
  19. else
  20. matrix[i][j] = -1;
  21. }
  22. }
  23. int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
  24. int distance = 0;
  25. while(!q.isEmpty()) {
  26. distance++;
  27. int size = q.size();
  28. for(int i = 0; i < size; i++) {
  29. Position pos = q.remove();
  30. for(int[] direction : directions) {
  31. int r = pos.row + direction[0];
  32. int c = pos.column + direction[1];
  33. if(r >= 0 && r < matrix.length && c >= 0 && c < matrix[0].length &&
  34. matrix[r][c] == -1) {
  35. matrix[r][c] = distance;
  36. q.add(new Position(r, c));
  37. }
  38. }
  39. }
  40. }
  41. return matrix;
  42. }
  43. }

Implementation 1 : Alternate approach

  1. class Solution {
  2. public int[][] updateMatrix(int[][] matrix) {
  3. if(matrix == null || matrix.length == 0)
  4. return matrix;
  5. Queue<int[]> q = new LinkedList<>();
  6. int rows = matrix.length, cols = matrix[0].length;
  7. for(int i = 0; i < rows; i++) {
  8. for(int j = 0; j < cols; j++) {
  9. if(matrix[i][j] == 0)
  10. q.add(new int[]{i,j});
  11. else
  12. matrix[i][j] = -1;
  13. }
  14. }
  15. int distance = 0;
  16. int[][] moves = {{0,1}, {0,-1}, {-1,0}, {1, 0}};
  17. while(!q.isEmpty()) {
  18. distance++;
  19. int size = q.size();
  20. for(int i = 0; i < size; i++) {
  21. int[] pos = q.remove();
  22. for(int[] move : moves) {
  23. int x = pos[0] + move[0];
  24. int y = pos[1] + move[1];
  25. if(x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] == -1){
  26. q.add(new int[]{x,y});
  27. matrix[x][y] = distance;
  28. }
  29. }
  30. }
  31. }
  32. return matrix;
  33. }
  34. }

Implementation 2 : BFS Approach

  1. class Solution {
  2. public int[][] updateMatrix(int[][] matrix) {
  3. if(matrix == null || matrix.length == 0)
  4. return matrix;
  5. int rows = matrix.length;
  6. int cols = matrix[0].length;
  7. Queue<int[]> q = new LinkedList<>();
  8. Set<String> set = new HashSet<>();
  9. for(int i = 0; i < rows; i++) {
  10. for(int j = 0; j < cols; j++) {
  11. if(matrix[i][j] == 0) {
  12. q.add(new int[]{i,j});
  13. set.add(i+","+j);
  14. }
  15. }
  16. }
  17. int[][] directions = { {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
  18. int step = 1;
  19. while(!q.isEmpty()) {
  20. int size = q.size();
  21. for(int i = 0; i < size; i++) {
  22. int[] pos = q.remove();
  23. for(int[] direction : directions) {
  24. int x = pos[0] + direction[0];
  25. int y = pos[1] + direction[1];
  26. if(x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] == 1 && !set.contains(x+","+y)) {
  27. matrix[x][y] = step;
  28. q.add(new int[]{x,y});
  29. set.add(x+","+y);
  30. }
  31. }
  32. }
  33. step++;
  34. }
  35. return matrix;
  36. }
  37. }

Implementation 2 : Dynamic Programming

  1. class Solution {
  2. public int[][] updateMatrix(int[][] matrix) {
  3. if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
  4. return matrix;
  5. int distanceUpperBound = matrix.length + matrix[0].length;
  6. for (int i = 0; i < matrix.length; i++) {
  7. for (int j = 0; j < matrix[0].length; j++) {
  8. if (matrix[i][j] != 0) {
  9. int topCell = (i > 0) ? matrix[i - 1][j] : distanceUpperBound;
  10. int leftCell = (j > 0) ? matrix[i][j - 1] : distanceUpperBound;
  11. matrix[i][j] = Math.min(topCell, leftCell) + 1;
  12. }
  13. }
  14. }
  15. for (int i = matrix.length - 1; i >= 0; i--) {
  16. for (int j = matrix[0].length - 1; j >= 0; j--) {
  17. if (matrix[i][j] != 0) {
  18. int bottomCell = (i < matrix.length - 1) ? matrix[i + 1][j] : distanceUpperBound;
  19. int rightCell = (j < matrix[0].length - 1) ? matrix[i][j + 1] : distanceUpperBound;
  20. matrix[i][j] = Math.min(Math.min(bottomCell, rightCell) + 1, matrix[i][j]);
  21. }
  22. }
  23. }
  24. return matrix;
  25. }
  26. }

References :

https://leetcode.com/problems/01-matrix/discuss/248525/Java-BFS-solution-with-comments

https://leetcode.com/problems/01-matrix/discuss/101051/Simple-Java-solution-beat-99-(use-DP)