刷题

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

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

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

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：

输入：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
mati is either 0 or 1.
mat 中至少有一个 0

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

二、思路分析：

本题给出了一个场景：求 mat 中对应位置元素到最近的 0 的距离。就是只能沿着横、竖到达另外一个点走的步数。从一个点出发求这种最短距离的方法很容易想到就是度优先遍历，即把周围这一圈搜索完成之后，再搜索下一圈，是慢慢扩大搜索范围的。

具体做法：

先将矩阵中所有为0的元素的坐标加入到队列，并且设置为已访问标识
从队列首取出元素，从当前节点扩散，扩散的条件是在矩阵范围内且并未被访问过。

同时我们还需要知道最先改变的位置坐标，肯定是最先到达点，也就是最近的，我们将该位置置为true，以后别人慢的到达该位置时，同样不能更改该位置的值

三、AC 代码：

class Solution {
    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};
    public int[][] updateMatrix(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;
        Queue<int[]> q=new LinkedList<>();
        boolean[][] flag=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    q.offer(new int[]{i,j});
                    flag[i][j]=true;
                } 
            }
        }
        while(!q.isEmpty()){
            int[] temp=q.poll();
            for(int t=0;t<4;t++){
                int x=temp[0]+dx[t];
                int y=temp[1]+dy[t];
                if(x>=0&&x<m&&y>=0&&y<n&&mat[x][y]==1&&!flag[x][y]){
                    q.offer(new int[]{x,y});
                    mat[x][y]=mat[temp[0]][temp[1]]+1;
                    flag[x][y]=true;
                }
            }
        }
        return mat;
    }
}

四、总结：

因为要求最近，所以一般会想到用bfs，如果要是求最远，一般会想到用dfs。

深度遍历模板思路： 第一步：明确递归参数 第二步：明确递归终止条件 第三步：明确递归函数中的内容 第四步：明确回溯返回值

广度遍历模板思路： 第一步：设置队列，添加初始节点 第二步：判断队列是否为空 第三步：迭代操作 弹出队列元素，进行逻辑处理 当前队列元素的下级元素，入队 第四步：在此执行步骤三

写题解不易，若对你有帮助，点赞评论再走吧。ヽ(✿ﾟ▽ﾟ)ノ，如有不足，请大家斧正。