剑指 Offer II 107. 矩阵中的距离

剑指 Offer II 107. 矩阵中的距离【中等题】

思路：

采用BFS层序遍历，找出所有的元素0，从元素0开始向四个方向层序遍历，设ans数组存储最近0距离，则ans中，mat矩阵元素0位置值为0，每层遍历遇到1则将ans值更新为元素0的ans值+1

代码：

class Solution {
    
    
    static int[][] ans;
    static int[][] dir = {
    {
    0,-1},{
    0,1},{
    -1,0},{
    1,0}};
    static int m,n;
    public static int[][] updateMatrix(int[][] mat) {
    
        m = mat.length;
        n = mat[0].length;
        //标记mat矩阵(i,j)位置元素是否被搜索过
        boolean[][] seen = new boolean[m][n];
        //存储mat矩阵中的0的位置坐标
        Queue<int[]> queue = new LinkedList<>();
        //存储mat矩阵(i,j)位置元素最近的0的距离
        ans = new int[m][n];
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (mat[i][j] == 0){
    
                    //将mat矩阵中元素0的位置坐标压入队列
                    queue.offer(new int[]{
    i,j});
                    //标记当前位置已被搜索过
                    seen[i][j] = true;
                }
            }
        }
        //BFS遍历，当栈中元素为空时，循环结束
        while(!queue.isEmpty()){
    
            //取出队列顶部元素0的位置
            int[] cell = queue.poll();
            //取出元素0的坐标
            int i = cell[0],j = cell[1];
            for (int k = 0; k < 4; k++) {
    
                //对元素0进行上下左右四个方向搜索，搜索到的位置坐标为(x,y)
                int x = i + dir[k][0],y = j + dir[k][1];
                //如果(x,y)未超出矩阵边界且(x,y)位置未被搜索过
                if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]){
    
                    //ans的(x,y)位置值 等于 ans的(i,j)位置值 + 1
                    ans[x][y] = ans[i][j] + 1;
                    //将(x,y)位置压入队列
                    queue.offer(new int[]{
    x,y});
                    //将(x,y)位置标记为已搜索
                    seen[x][y] = true;
                }
            }
        }
        return ans;
    }
}