题目
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example1：
image.png
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Example2:
image.png
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
解题思路
这道题的要求是求出每个cell到0的距离，可以用BFS和DP两种方法来做。
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| BFS | O(mn) | O(mn) |
| DP | O(4mn) | O(1) |
1. BFS
BFS的思路是，找到起点节点，然后以起点为圆心，一层一层扩散的方式，遍历所有的节点。
BFS的实现模板，就是使用队列来实现。
模板代码如下：
private void bfs(Node root){
Queue<Node> queue = new LinkedList<>();
// 先把起点加入队列
queue.offer(root);
while(!queue.isEmpty()){
int node = queue.poll();
// 把所有的下一层级的孩子，加入队列
for(Node child : node.children){
queue.offer(child);
}
}
}
这道题是典型的BFS的思路。
- 题目要求节点到0的距离，所以我们知道，所有0节点的值都是0。那我们可以把这个0节点作为起点，先加入队列。
- 记录一个全局的变量level，表示节点离0节点的层数。
- 然后找到0节点周围的所有1节点，遍历他们，并设置层数level，然后将这些节点加入队列，继续遍历。
- 直到所有的节点都遍历完。
注意：为了防止重复遍历死循环，已经遍历过的节点，不要重复遍历。
class Solution {
public int[][] updateMatrix(int[][] mat) {
int n = mat.length, m = mat[0].length;
int[][] res = new int[n][m];
// 保存已经遍历过的节点
boolean[][] visited = new boolean[n][m];
// BFS模板代码
Queue<int[]> queue = new LinkedList<>();
for(int i = 0 ; i < n; i++){
for(int j = 0; j < m; j++){
// 先把所有的0节点加入queue，作为起点
if(mat[i][j] == 0){
visited[i][j] = true;
queue.add(new int[]{i, j});
}
}
}
// 遍历四个方向的节点
int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
while(!queue.isEmpty()){
int[] cur = queue.poll();
int i = cur[0], j = cur[1];
for(int k = 0; k < directions.length; k++){
int r = i + directions[k][0];
int c = j + directions[k][1];
// 判断坐标值是否有效 & 是否访问过
if(r >= 0 && r < n && c >= 0 && c < m && !visited[r][c]){
res[r][c] = res[i][j] + 1;
visited[r][c] = true;
queue.add(new int[]{r, c});
}
}
}
return res;
}
}
2. DP
这道题很直接得能想到用DP去做。递推公式如下：
如果mat[i][j] == 0 则 dp[i][j] = 0
如果mat[i][j] != 0 则 dp[i][j] = 1 + min(dp[i-1][j], dp[i+1][j], [dp[i][j-1], dp[i][j+1])
一般DP都是从一个方向开始，做DP。而这道题需要从四个方向分别做DP，最后取DP结果的最小值。
class Solution {
public int[][] updateMatrix(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
int[][] dp = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(mat[i][j] == 0){
dp[i][j] = 0;
}else{
dp[i][j] = Math.max(n, m) + 1;
}
}
}
// 从左上方来的
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i > 0){
dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);
}
if(j > 0){
dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);
}
}
}
// 从左下方来
for(int i = n - 1; i >= 0; i--){
for(int j = 0; j < m; j++){
if(i < n-1){
dp[i][j] = Math.min(dp[i][j], dp[i+1][j] + 1);
}
if(j > 0){
dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);
}
}
}
// 从右上方来
for(int i = 0; i < n; i++){
for(int j = m-1; j >= 0; j--){
if(i > 0){
dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);
}
if(j < m-1){
dp[i][j] = Math.min(dp[i][j], dp[i][j+1] + 1);
}
}
}
// 从右下方来
for(int i = n-1; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
if(i < n-1){
dp[i][j] = Math.min(dp[i][j], dp[i+1][j] + 1);
}
if(j < m-1){
dp[i][j] = Math.min(dp[i][j], dp[i][j+1] + 1);
}
}
}
return dp;
}
}
总结
这道题我们用了BFS和DP两种方法来做，两种方法都比较直观。有几点需要注意：
- BFS采用以0为起点的方法，多路同时进行。为了避免发生死循环，需要记录已经访问过的节点。
- DP需要从四个方向做DP，然后取最小值作为结果，如果只从一个方向DP，结果不是最优解。
