「力扣」第 542 题：01 矩阵（中等）

• 题目链接：542. 01 矩阵 (opens new window)。

题目描述

给定一个由 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
• mat[i][j] is either 0 or 1.
• mat 中至少有一个 0

说明：因时间和精力关系，本题没有写详解，只给出了参考代码。读者可以在「力扣」这道题的评论区和题解区找到适合自己的思路分析和代码。如果确实需要我编写具体的解题思路，可以发邮件到 liweiwei1419@gmail.com。

参考代码：

import java.util.LinkedList;
import java.util.Queue;


public class Solution {

    public int[][] updateMatrix(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return new int[0][0];
        }
        int cols = matrix[0].length;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    // 从为 0 的地方开始向外扩散
                    queue.add(getIndex(i, j, cols));
                } else {
                    // 设置成一个特殊值，说明当前这个坐标的位置还没有被扩散到
                    matrix[i][j] = -1;
                }
            }
        }

        int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        // 从为 0 的地方开始进行广度优先遍历
        while (!queue.isEmpty()) {
            // 当前的位置，一开始的时候，"0" 正好，到"0" 的距离也是 0 ，符合题意
            Integer head = queue.poll();

            int currentX = head / cols;
            int currentY = head % cols;

            // 现在要往 4 个方向扩散
            for (int i = 0; i < 4; i++) {
                int newX = currentX + directions[i][0];
                int newY = currentY + directions[i][1];
                // 在有效的坐标范围内，并且还没有被访问过
                if (inArea(newX, newY, rows, cols) && matrix[newX][newY] == -1) {
                    matrix[newX][newY] = matrix[currentX][currentY] + 1;
                    queue.add(getIndex(newX, newY, cols));
                }
            }
        }
        return matrix;
    }

    /**
     * @param x    二维表格单元格横坐标
     * @param y    二维表格单元格纵坐标
     * @param cols 二维表格列数
     * @return
     */
    private int getIndex(int x, int y, int cols) {
        return x * cols + y;
    }


    /**
     * @param x    二维表格单元格横坐标
     * @param y    二维表格单元格纵坐标
     * @param rows 二维表格行数
     * @param cols 二维表格列数
     * @return
     */
    private boolean inArea(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}

参考资料

• 官方题解：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
• https://blog.csdn.net/u014593748/article/details/65937524

---

作者：liweiwei1419 链接：https://suanfa8.com/breadth-first-search/solutions-1/0542-01-matrix 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。