每日一题- 01 矩阵

墨蓝 2023-05-22 04:37 5阅读 0赞

今天是2020年4月15日，星期三。

### 题目描述 ###

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

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

示例 1:  
输入:

0 0 0
    0 1 0
    0 0 0

输出:

0 0 0
    0 1 0
    0 0 0

示例 2:  
输入:

0 0 0
    0 1 0
    1 1 1

输出:

0 0 0
    0 1 0
    1 2 1

注意:

给定矩阵的元素个数不超过 10000。  
给定矩阵中至少有一个元素是 0。  
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

### 题目分析 ###

这个题目与前几天的每日一题 [1162.地图分析][1162.] 相同，形式上都是找距离1/0最近的0/1。总结起来看是典型的广度优先遍历(BFS)的问题。在大学时学习数据结构与算法时，我们就知道，在广度优先遍历时，需要借助队列。

本题目中，是要找距离1最近的0的距离，可以转换为距离0最近的1的距离。在遍历时，遇到0则加入队列，遇到1将其值改为-1。若某一个值为-1，则表明其还未被访问过。

参考甜姨的题解，总结了一下几点BFS的套路:

1.  一般借助队列来实现
2.  对于【树的单源root】的遍历 - 典型的单源BFS类型
    
     *  首先将root入队列，在按照左孩子、右孩子的方式一个一个去遍历，相当于就是【按层去遍历】。
3.  对于【图的多个节点】的遍历 - 典型的多源BFS类型
    
     *  对于图的多个节点的遍历与树的单源的遍历的区别：
        
         *  Tree的Root只有一个，所以只需要将root入队列即可；
         *  图的源点有多个，需要将每个源都需要入队列
     *  需要注意的问题：
        
         *  因为Tree本身是有向的，分层的，所以不需要表示是否已经访问过了；
         *  对于无向图来说，必须标志某一个节点是否已经访问了。为了防止同一个节点多次入队列，需要在访问前，就将该节点设置为已访问状态。

### 参考代码 ###

/**
     * 还是参考甜姨的题解，在总结一下bfs类型题目的套路，见包路径下"bfs类型套路总结"
     * 从0开始向外扩散到1，计算距离1最近的0的距离
     */
    public int[][] updateMatrix(int[][] matrix) {
        int[][] result = new int[matrix.length][matrix[0].length];
    
        if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
            return result;
        }
        Queue<int[]> queue = new LinkedList<>();
        int rows = matrix.length;
        int cols = matrix[0].length;
    
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = -1;
                }
            }
        }
        // 标识左右方向值
        int[] fowardX = new int[]{-1, 1, 0, 0};
        int[] fowardY = new int[]{0, 0, -1, 1};
    
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0];
            int y = point[1];
            for (int i = 0; i < 4; i++) {
                int newX = x + fowardX[i];
                int newY = y + fowardY[i];
                // 如果四邻域的点是 -1，表示这个点是未被访问过的 1
                // 所以这个点到 0 的距离就可以更新成 matrix[x][y] + 1。
                if (newX >= 0 && newY >= 0 && newX < rows && newY < cols && matrix[newX][newY] == -1) {
                    matrix[newX][newY] = matrix[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
    
        return matrix;
    }

### 说在最后 ###

大家可以如果想要早刷题监督组织的，可以来加入我们的组织，目前已经有五百人了。LeetCode大佬甜姨、威威大佬和群主都很厉害。我们的打卡网址：[http://group.ojeveryday.com/\#/check][http_group.ojeveryday.com_check]；期待大家的加入。  
![每日一题打卡][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MTM1NDIx_size_16_color_FFFFFF_t_70]

[1162.]: https://leetcode-cn.com/problems/as-far-from-land-as-possible/
[http_group.ojeveryday.com_check]: http://group.ojeveryday.com/#/check
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MTM1NDIx_size_16_color_FFFFFF_t_70]: /images/20230521/91804a58156b4c7687a163ee10ede856.png