版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434834
本次周赛主要分为一下4道题:
Problem:
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distances between two adjacent cells is 1.
Example 1:
Input: 000010000 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0 \ \end{matrix}undefined Output: 000010000 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0 \ \end{matrix}
Example 2:
Input: 001011001 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 1 & 1 & 1 \ \end{matrix}undefined Output: 001012001 \begin{matrix} 0 & 0 & 0 \ 0 & 1 & 0 \ 1 & 2 & 1 \ \end{matrix}
Note:
我的思路永远是复杂的,也不知道为啥,难道是受其他题目的影响,还是做的不够多,见识不够广咧。第一反映居然是dfs,刚开始不以为然,不就是从某个位置为1开始,从四个方向找最近的零元素么!但当提交代码后才发现,我去,最近0元素未必一定是在它遍历的四个方向上,遍历可以拐弯!那dfs怎么做?至少我所知道的dfs压根没法解决递归过程中改变方向的问题。
唉,所以又得换思路了,而bfs在我脑海中未成型,很难想到它的应用,自然也就无法形成答案。所以我是照着discuss中的bfs解决方案来模拟它的求解过程的,方便自己理解。我们直接拿第二个例子来解释。
inf在此处表示无穷,在Java代码中,用Integer.MAX_VALUE
来表示。在对它变换的同时,由于已经扫描了一遍矩阵,在此过程中还需要记录所有0元素的row,col
值,并放入一个队列中。
接下来是求解的核心了,我们只需要寻找到一种机制能够准确更新该数组就可以了,并且它的更新规则符合题意。刚才的dfs是在一个方向上遍历到底,没法拐弯,问题的关键在于隔壁的1元素是否携带了有效信息供当前节点参考!很明显,dfs方案一条路走到底,每个1元素忽略另外三个方向的信息,所以自然而然无法求出正确的。
而再来看看bfs,用形象的比喻来描述这道题的话,就是一颗石头扔入湖中时,它的影响波及周围,且向四周不断传播它的影响。所以该算法的思想,就是首先把这些石头找出来咯【0元素】,更新规则是,一旦碰到【inf】,我就设一个该【0元素】对【inf】的影响值,此处为1。但由于【0元素】的影响是传递的,所以受它影响的【inf】节点必须得放入队列中,计算下次影响值。碰到【inf】,则+1,但前提是当前【inf】节点的值大于原先的值+1。
第二次更新:
00101inf001
\begin{matrix} 0 & 0 & 0 \ 0 & 1& 0 \ 1& inf & 1\ \end{matrix}
0元素周围的元素均被波及,接下来就是1元素的传递,传递的还是0元素的影响。
第三次更新:
001012001
\begin{matrix} 0 & 0 & 0 \ 0 & 1& 0 \ 1& 2& 1\ \end{matrix}
public List<List<Integer>> updateMatrix(List<List<Integer>> 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}); //把0元素加入队列中,以备波及影响周围元素
}
else {
matrix.get(i).set(j, Integer.MAX_VALUE);//设为最大值,方便求0元素影响值
}
}
}
//溅起的涟漪,代表传播的四个方向
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];
//不符合条件的均跳过,找来的比如:0 的周围 还是0的哪些元素,1的周围是1,但不符合影响值更新规则的同样忽略。
if (r < 0 || r >= m || c < 0 || c >= n ||
matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1) continue;
//把受0波及的1元素也放入队列中,涟漪是会持续的。
queue.add(new int[] {r, c});
matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
}
}
return matrix;
}
好了,现在代码是不是就容易理解了,该问题的核心思想就是bfs的涟漪传播,解决方案只能说太妙了,不看答案想不到。但反过头来看看bfs和dfs,是不是也能比较出一些区别了呢?起码这道题加深了我对bfs的认知,以及理解了dfs的局限性。