leetcode 542. 01 Matrix | 542. 01 矩阵（图解，广度优先搜索）

妖狐艹你老母 2022-09-02 04:26 128阅读 0赞

## 题目 ##

[https://leetcode.com/problems/01-matrix/][https_leetcode.com_problems_01-matrix]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

这题很有趣，图解一下思路吧~

可以想象成“感染”的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
从 1 开始逐层向外扩散，感染的数字 depth 每轮 +1，直到所有格子全部感染为止。

为了避免重复路径，每次判断即将感染的格子是否大于当前的感染数字 depth。

class Solution { 
        int M;
        int N;
    
        public int[][] updateMatrix(int[][] mat) { 
            int count = 0;
            M = mat.length;
            N = mat[0].length;
    
            int[][] dst = new int[M][N]; // distance
            for (int i = 0; i < M; i++) { 
                for (int j = 0; j < N; j++) { 
                    if (mat[i][j] == 0) { 
                        dst[i][j] = 0;
                        count++;
                    } else { 
                        dst[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
    
            int depth = 0;
            while (count != M * N) { 
                for (int i = 0; i < M; i++) { 
                    for (int j = 0; j < N; j++) { 
                        if (dst[i][j] == depth) { 
                            if (i > 0 && depth + 1 < dst[i - 1][j]) {  // left
                                dst[i - 1][j] = depth + 1;
                                count++;
                            }
                            if (i < M - 1 && depth + 1 < dst[i + 1][j]) {  // right
                                dst[i + 1][j] = depth + 1;
                                count++;
                            }
                            if (j > 0 && depth + 1 < dst[i][j - 1]) {  // up
                                dst[i][j - 1] = depth + 1;
                                count++;
                            }
                            if (j < N - 1 && depth + 1 < dst[i][j + 1]) {  // down
                                dst[i][j + 1] = depth + 1;
                                count++;
                            }
                        }
                    }
                }
                depth++;
            }
            return dst;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_01-matrix]: https://leetcode.com/problems/01-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/9357e209004249b19fcf02c31dfa7fa7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/b7cd34b9104247f5a90bccec5f642ca9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/28ee6b75525b4e2e955398881b8fb7c5.png