題目
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兩種方法來做稻轨。
| 方法 | 時間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|
| BFS | O(mn) | O(mn) |
| DP | O(4mn) | O(1) |
1. BFS
BFS的思路是缚去，找到起點節(jié)點，然后以起點為圓心樟结，一層一層擴散的方式养交，遍歷所有的節(jié)點。
BFS的實現(xiàn)模板瓢宦，就是使用隊列來實現(xiàn)碎连。
模板代碼如下：
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的思路驮履。
- 題目要求節(jié)點到0的距離鱼辙，所以我們知道，所有0節(jié)點的值都是0玫镐。那我們可以把這個0節(jié)點作為起點倒戏，先加入隊列。
- 記錄一個全局的變量level恐似，表示節(jié)點離0節(jié)點的層數(shù)杜跷。
- 然后找到0節(jié)點周圍的所有1節(jié)點，遍歷他們，并設(shè)置層數(shù)level葱椭，然后將這些節(jié)點加入隊列捂寿，繼續(xù)遍歷。
- 直到所有的節(jié)點都遍歷完孵运。
注意：為了防止重復(fù)遍歷死循環(huán)秦陋，已經(jīng)遍歷過的節(jié)點，不要重復(fù)遍歷治笨。
class Solution {
public int[][] updateMatrix(int[][] mat) {
int n = mat.length, m = mat[0].length;
int[][] res = new int[n][m];
// 保存已經(jīng)遍歷過的節(jié)點
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節(jié)點加入queue驳概，作為起點
if(mat[i][j] == 0){
visited[i][j] = true;
queue.add(new int[]{i, j});
}
}
}
// 遍歷四個方向的節(jié)點
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];
// 判斷坐標(biāo)值是否有效 & 是否訪問過
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結(jié)果的最小值等孵。
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;
}
}
總結(jié)
這道題我們用了BFS和DP兩種方法來做稚照，兩種方法都比較直觀。有幾點需要注意：
- BFS采用以0為起點的方法俯萌，多路同時進(jìn)行果录。為了避免發(fā)生死循環(huán)，需要記錄已經(jīng)訪問過的節(jié)點咐熙。
- DP需要從四個方向做DP弱恒，然后取最小值作為結(jié)果，如果只從一個方向DP棋恼，結(jié)果不是最優(yōu)解返弹。
