LeetCode_BFS_中等_542.01 矩阵

落日映苍穹つ 2023-10-07 20:47 42阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

**示例 1：**

![在这里插入图片描述][f84a47ee662d4e0c9ba4d9d0f1227a87.png]  
输入：mat = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
输出：\[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]

**示例 2：**

![在这里插入图片描述][826c2217f88742ed824960d5c55ba676.png]  
输入：mat = \[\[0,0,0\],\[0,1,0\],\[1,1,1\]\]  
输出：\[\[0,0,0\],\[0,1,0\],\[1,2,1\]\]

**提示：**  
m == mat.length  
n == mat\[i\].length  
1 <= m, n <= 104  
1 <= m \* n <= 104  
mat\[i\]\[j\] is either 0 or 1.  
mat 中至少有一个 0

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/01-matrix

## 2.思路 ##

（1）BFS

## 3.代码实现（Java） ##

//思路1————BFS
    class Solution {
        
        public int[][] updateMatrix(int[][] mat) {
        
            int m = mat.length;
            int n = mat[0].length;
            int[][] res = new int[m][n];
            // dirs 记录遍历的四个方向
            int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, 1}, {
        0, -1}};
            Queue<int[]> queue = new ArrayDeque<>();
            // visited[i][j] = true 表示坐标为 (i, j) 的格子已经被访问过
            boolean[][] visited = new boolean[m][n];
            //将 mat 中所有的 0 添加到初始队列中
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (mat[i][j] == 0) {
        
                        queue.offer(new int[]{
        i, j});
                        visited[i][j] = true;
                    }
                }
            }
            // BFS
            while (!queue.isEmpty()) {
        
                int[] cell = queue.poll();
                int i = cell[0];
                int j = cell[1];
                //朝 4 个方向进行遍历
                for (int d = 0; d < 4; d++) {
        
                    int nextI = i + dirs[d][0];
                    int nextJ = j + dirs[d][1];
                    //考虑边界
                    if (!visited[nextI][nextJ] && nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n) {
        
                        res[nextI][nextJ] = res[i][j] + 1;
                        queue.offer(new int[]{
        nextI, nextJ});
                        visited[nextI][nextJ] = true;
                    }
                }
            }
            return res;
        }
    }

[f84a47ee662d4e0c9ba4d9d0f1227a87.png]: https://img-blog.csdnimg.cn/f84a47ee662d4e0c9ba4d9d0f1227a87.png
[826c2217f88742ed824960d5c55ba676.png]: https://img-blog.csdnimg.cn/826c2217f88742ed824960d5c55ba676.png