【LeetCode】01 Matrix 解题报告
标签（空格分隔）： LeetCode
题目地址：https://leetcode.com/problems/01-matrix/#/description
题目描述：
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：
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:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
Ways
这个题的思想是BFS，广度优先遍历。也是让我学习了一下到底怎么写BFS。
首先，BFS要用到了队列，让值为0的节点全部进入队列，代表要进行遍历的点；把值为1的点设为最大值，表示距离很远，初始状态下不能到。然后对于队列中的每个点都有四个方向，要考虑这个点临近的四个方向的点距都离为当前点到0点的距离加1.有点类似DP，把某个点到0的距离设为周围点到0的最短值+1即可。注意，遍历时修改完另外点的值的时候，一定要把这个节点也加入到队列中。这个点到0的距离是最近距离+1，而不是单纯的1.
public class Solution {
public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
if(matrix == null || matrix.size() == 0){
return matrix;
}
int m = matrix.size();
int n = matrix.get(0).size();
Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix.get(i).get(j)==0){
queue.offer(new int[]{i, j});
}else{
matrix.get(i).set(j, Integer.MAX_VALUE);
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!queue.isEmpty()){
int cell[]= queue.poll();
for(int[] d: dirs){
int r = cell[0] + d[0];
int c = cell[1] + d[1];
if (r < 0 || r >= m || c < 0 || c >= n ||
matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1)
continue;
queue.offer(new int[]{r, c});
matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
}
}
return matrix;
}
}Date
2017 年 4 月 11 日