542.01矩阵解析

古城微笑少年丶 2023-10-11 17:07 48阅读 0赞

题目描述：

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

示例1：

> ![在这里插入图片描述][e498d67c97a14d72997f0ce5f4fa8bf9.png_pic_center]

> 输入：mat = \[ \[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
> 输出：\[ \[0,0,0\],\[0,1,0\],\[0,0,0\]\]

示例2：

> ![在这里插入图片描述][5ccbd8d095aa45bab43822c862ea1713.png_pic_center]

> 输入：mat = \[ \[0,0,0\],\[0,1,0\],\[1,1,1\]\]  
> 输出：\[ \[0,0,0\],\[0,1,0\],\[1,2,1\]\]

本题是一道很典型的广度优先搜索类型的题目，对于广度优先搜索的两个模板，请大家务必烂熟于心  
BFS 使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS 总共有两个模板：

*  1.如果不需要确定当前遍历到了哪一层，BFS 模板如下。

while queue 不空：
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未访问过：
                queue.push(该节点)

*  2.如果要确定当前遍历到了哪一层，BFS 模板如下。  
    这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
    while queue 不空：
        size = queue.size()
        while (size -->0) {
        
            cur = queue.pop()
            for 节点 in cur的所有相邻节点：
                if 该节点有效且未被访问过：
                    queue.push(该节点)
        }
        level ++;

而这道题目我们就可以利用广度优先的分层思想，我们可以看到1有哪几种情况呢，就题目中给出的示例来说：

*  1.上下左右四个方向至少含有1个0
 *  2.上下左右四个方向均没有0，全部被1包围，且其中至少一个1符合第一种情况

我们按照这种思路，我们扩展n\*n的矩阵  
我们继续按照上面的思路展开第三、第四…第n中情况

*  3.上下左右被1包围，且其中至少有一个1符合第二种情况
 *  4.上下左右被1包围，且其中至少有一个1符合第三种情况  
    于是能给出以下类型的矩阵：  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

这种矩阵就是按照我们的分层的思路画出来的，我们可以看到第一层也就是最外面的一层全部是0，我们不用考虑，其最短路径就是i-1即1-1=0  
第二层的1被至少一个0包围，最短路径就是i-1=2-1=1，以此类推，所以我们要做的就是将题目给出的矩阵按照分层的思路进行转换，转化为上面这种类型的矩阵，那么每一层怎么找呢？  
首先0我们不用管，如果是1，且周围至少有一个0的话，我们就让他们进入队列，当第一层走完之后，开始找与第一层相邻且未访问过的1，让其入队，同时路径长度可以设置为2，以此类推。。。  
通俗来说，思路如下 ：

*  1.将所有被0包裹的1入队，同时设置level为1
 *  2.将所有被第一层包裹且未被访问的1入队，同时level设置为2
 *  3.重复以上两个过程，注意level需要一直往上加

带着上面的思路看一下代码，注意代码里有详细的注释，请耐心读完  
代码如下：

import java.util.*;
    
    /**
     * 题目：0 1矩阵
     * 题目编号：542
     * 题目链接：https://leetcode-cn.com/problems/01-matrix/
     */
    public class 矩阵01_542 {
        
        /**
         * 是否还在矩阵中
         * 在：true
         */
        public static boolean inBound(int x, int y, int[][] grid) {
        
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
        
                return true;
            } else return false;
        }
    
        public static int[][] updateMatrix(int[][] mat) {
        
            int row = mat.length;//行数
            if (row <= 0) return mat;
            int column = mat[0].length;//列数
            //定义上下左右四个移动方向
            int[] dx = {
        0, 0, -1, 1};
            int[] dy = {
        -1, 1, 0, 0};
            boolean[][] visted = new boolean[row][column];//存储
            Queue<int[]> queue = new LinkedList<>();//记录移动点的坐标
            for (int i = 0; i < row; i++) {
        //遍历整个棋盘，让第一层的1入队
                for (int j = 0; j < column; j++) {
        
                    if (mat[i][j] == 0) {
        
                        visted[i][j] = true;
                    }
                    if (mat[i][j] == 1) {
        //首先把第一层的1放入队列
                        int count = 0;//用来记录上下左右有没有0，一旦发现有0就会计数
                        for (int index = 0; index < 4; index++) {
        
                            int next_x = i + dx[index];
                            int next_y = j + dy[index];
                            if (inBound(next_x, next_y, mat) && mat[next_x][next_y] == 0) {
        //第一层的1必定上下左右至少有一个0
                                count++;
                            }
                        }
                        if (count > 0) {
        //说明上下左右中至少一个0符合第一层的1的定义，可以入队 队列第一层
                            queue.add(new int[]{
        i, j});
                            visted[i][j] = true;
    
    
                        }
                    }
    
                }
            }
            int level = 1;//由于第一层的1已经 入队，所以level设置为1
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                while (size-- > 0) {
        //用来判断这一层是否结束
                    int[] t = queue.poll();
                    int x = t[0], y = t[1];
                    mat[x][y] = level;
                    //开始找下一层的信息
                    for (int i = 0; i < 4; i++) {
        
                        int next_x = x + dx[i];
                        int next_y = y + dy[i];
                        if (inBound(next_x, next_y, mat) && !visted[next_x][next_y]) {
        
                            queue.add(new int[]{
        next_x, next_y});
                            visted[next_x][next_y] = true;
                        }
                    }
                }
                level++;//每一层一旦遍历结束就加一层
            }
            return mat;
        }
    
        public static void print(int[][] mat) {
        
            for (int i = 0; i < mat.length; i++) {
        
                for (int j = 0; j < mat[0].length; j++) {
        
                    System.out.print(mat[i][j] + " ");
                }
                System.out.println();//换行
            }
        }
    
        public static void main(String[] args) {
        
            int[][] mat = {
        {
        0, 0, 0}, {
        0, 1, 0}, {
        1, 1, 1}};
            print(mat);
            System.out.println("-------------------------------");
            print(updateMatrix(mat));
        }
    }

[e498d67c97a14d72997f0ce5f4fa8bf9.png_pic_center]: https://img-blog.csdnimg.cn/e498d67c97a14d72997f0ce5f4fa8bf9.png#pic_center
[5ccbd8d095aa45bab43822c862ea1713.png_pic_center]: https://img-blog.csdnimg.cn/5ccbd8d095aa45bab43822c862ea1713.png#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/e36084429ce04987844cad84c4055489.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWk5pbmVTdW4=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center