542 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.
Example 1:
Input:
0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2:
Input:
0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
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.
(1) BFS
class Solution {
public int[][] updateMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return matrix;
}
Queue<int[]> queue = new LinkedList<>();
int m = matrix.length, n = matrix[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
queue.add(new int[] {i, j});
}
else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
while (!queue.isEmpty()) {
int[] cell = queue.remove();
int curRow = cell[0], curCol = cell[1];
for (int[] direction : directions) {
int nextRow = curRow + direction[0];
int nextCol = curCol + direction[1];
if (isValid(matrix, curRow, curCol, nextRow, nextCol)) {
matrix[nextRow][nextCol] = matrix[curRow][curCol] + 1;
queue.add(new int[] {nextRow, nextCol});
}
}
}
return matrix;
}
public boolean isValid(int[][] matrix, int curRow, int curCol, int nextRow, int nextCol) {
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[nextRow][nextCol] > matrix[curRow][curCol] + 1;
}
}
(2) DFS
class Solution {
public int[][] updateMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return matrix;
}
int m = matrix.length, n = matrix[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 0) {
dfs(i, j, matrix, directions);
}
}
}
return matrix;
}
public void dfs(int row, int col, int[][] matrix, int[][] directions) {
int dist = Integer.MAX_VALUE;
for (int[] direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (isValid(nextRow, nextCol, matrix)) {
dist = Math.min(dist, matrix[nextRow][nextCol] + 1);
}
}
if (dist != matrix[row][col]) {
matrix[row][col] = dist;
for (int[] direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (isValid(nextRow, nextCol, matrix)) {
dfs(nextRow, nextCol, matrix, directions);
}
}
}
}
public boolean isValid(int nextRow, int nextCol, int[][] matrix) {
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length;
}
}
BFS: 时间复杂度O(mn), 空间复杂度O(mn)
DFS: 时间复杂度O(mn), 空间复杂度O(mn)
Last modified 3yr ago