1.题目描述
2.思路
总结：用广度优先搜索，首先要确定0的位置，不为0的位置，我们要更新的它的值，只能往上下左右寻找跟它最近的0的位置。
解题思路
我们用 BFS（广度优先搜索）求解，因为 BFS 可以保证最短路径。计算出每个 1 到最近的 0 的最短距离。
步骤：
初始化队列
先找到所有的 0，把它们的坐标 (i, j) 放入队列 queue，并初始化 dist[i][j] = 0。
其他的 1 先标记为 -1，表示未计算。
BFS 计算最短距离
每次从 queue 取出一个 (i, j) 位置的 0，尝试向 四个方向（上、下、左、右）扩展：
如果新位置是 -1（未计算），就更新它的 dist 值 = 当前值 +1，然后把它加入 queue 继续处理。
BFS 遍历所有 1，把 -1 变成最短距离，直到 队列为空。⚡ 结束条件：
队列 queue 为空时，所有 1 都已经更新，算法结束。✅ 先把 0 入队，1 变 -1
✅ 从 0 开始 BFS，层层扩展
✅ BFS 遍历完所有 1，队列为空时结束
这样，最终矩阵每个 1 的值就是它到最近 0 的最短距离！
例子1：
个人总结：0值保持不变，1值赋值为-1.从0的位置出发，上下左右扫描，遇到-1，将距离更新为1并且赋值给当前遇到的元素。从当前元素（比如1）出发遇到值为-1的继续更新，并把此时距离2赋值给当前遇到的-1.以此类推，从当前元素（比如2）出发，遇到值为-1的值再次更新，并把此时距离=3赋值给遇到的-1.
例子2：
在这里插入图片描述
3.代码实现
方法一：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;//计算初始二维数组的行数
int n = mat[0].length;//计算初始二维数组的列数
int[][] dist = new int[m][n];
//定义一个队列
Queue<int[]> s1 = new LinkedList<>();
//LinkedList<>（常用，支持 FIFO 队列）
// 1. 初始化：找到所有 0，设定距离，1 设为 -1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
s1.offer(new int[]{i, j});
//new int[]{i, j} 这里是 一维数组，它的作用是将 (i, j) 这个坐标存入队列。
} else {
dist[i][j] = -1;
}
}
}
// 2.方向数组（上、下、左、右）
int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
// 2. BFS 遍历所有 1，更新最近 0 的距离
while (!s1.isEmpty()) {
//队列 queue 是 Queue<int[]>，即存储的是一维数组 int[]，每个 int[] 代表一个坐标点 (x, y)。
//queue.poll() 返回的是 queue 里存储的 int[] 数组，它的结构是 [x, y]，即一个一维数组，包含两个整数（行号 x 和列号 y）。
int[] curr = s1.poll();//存储当前坐标的一维数组,长度为 2 的一维数组。
//for (int i = 0; i < directions.length; i++) {
// int dx = directions[i][0];
// int dy = directions[i][1];
//
// int newX = x + dx;
// int newY = y + dy;
//}
for (int[] dir : directions) {
// dir = {-1, 0}，dir = {1, 0}，{1,0},{-1,0}
int newX = curr[0] + dir[0];
int newY = curr[1] + dir[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && dist[newX][newY] == -1) {
//dist[newX][newY]==-1,说明刚开始0的元素附近为1的元素把他们设置为-1，dist[newX][newY]为0附近的元素
dist[newX][newY]=dist[curr[0]][curr[1]]+1;
s1.offer(new int[]{newX,newY});
}
}
}
return dist;
// 检查边界 & 是否未计算
}
}
带测试方法：
import java.util.LinkedList;
import java.util.Queue;
public class test05 {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;//计算初始二维数组的行数
int n = mat[0].length;//计算初始二维数组的列数
int[][] dist = new int[m][n];
//定义一个队列
Queue<int[]> s1 = new LinkedList<>();
//LinkedList<>（常用，支持 FIFO 队列）
// 1. 初始化：找到所有 0，设定距离，1 设为 -1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
s1.offer(new int[]{i, j});
//new int[]{i, j} 这里是 一维数组，它的作用是将 (i, j) 这个坐标存入队列。
} else {
dist[i][j] = -1;
}
}
}
// 2.方向数组（上、下、左、右）
int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
// 2. BFS 遍历所有 1，更新最近 0 的距离
while (!s1.isEmpty()) {
//队列 queue 是 Queue<int[]>，即存储的是一维数组 int[]，每个 int[] 代表一个坐标点 (x, y)。
//queue.poll() 返回的是 queue 里存储的 int[] 数组，它的结构是 [x, y]，即一个一维数组，包含两个整数（行号 x 和列号 y）。
int[] curr = s1.poll();//存储当前坐标的一维数组,长度为 2 的一维数组。
//for (int i = 0; i < directions.length; i++) {
// int dx = directions[i][0];
// int dy = directions[i][1];
//
// int newX = x + dx;
// int newY = y + dy;
//}
for (int[] dir : directions) {
// dir = {-1, 0}，dir = {1, 0}，{1,0},{-1,0}
int newX = curr[0] + dir[0];
int newY = curr[1] + dir[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && dist[newX][newY] == -1) {
//dist[newX][newY]==-1,说明刚开始0的元素附近为1的元素把他们设置为-1，dist[newX][newY]为0附近的元素
dist[newX][newY]=dist[curr[0]][curr[1]]+1;
s1.offer(new int[]{newX,newY});
}
}
}
return dist;
// 检查边界 & 是否未计算
}
public static void main(String[] args){
test05 solution = new test05();
int[][] mat={
{0, 0, 0},
{0, 1, 0},
{1, 1, 1}
};
int[][] reasult= solution.updateMatrix(mat);
for(int[] row:reasult)
{
for(int num:row)
{
System.out.print(num+" ");
}
System.out.println();
}
}
}
关键代码：
// 2. BFS 遍历
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int[] dir : directions) {
int newX = x + dir[0];
int newY = y + dir[1];
// 检查边界 & 是否未访问
if (newX >= 0 && newX < m && newY >= 0 && newY < n && dist[newX][newY] == -1) {
dist[newX][newY] = dist[x][y] + 1; // 正确更新距离
queue.offer(new int[]{newX, newY}); // 加入队列
}
}
}
补充队列的offer和poll用法
queue.offer（）和queue.poll()的用法
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// 创建一个队列（FIFO：先进先出）
Queue<Integer> queue = new LinkedList<>();
// 向队列中添加元素
queue.offer(10);
queue.offer(20);
queue.offer(30);
System.out.println("队列内容：" + queue); // [10, 20, 30]
// 取出队列头部元素（不删除）
System.out.println("队头元素：" + queue.peek()); // 10
// 取出并删除队列头部元素
System.out.println("出队元素：" + queue.poll()); // 10
System.out.println("队列内容：" + queue); // [20, 30]
}
}
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> pq = new PriorityQueue<>();
// 添加元素
pq.offer(30);
pq.offer(10);
pq.offer(20);
System.out.println("队列内容：" + pq); // [10, 30, 20] (内部最小堆)
// 取出最小的元素（自动排序）
System.out.println("出队元素：" + pq.poll()); // 10
System.out.println("出队元素：" + pq.poll()); // 20
//queue.poll() 与 remove() 类似，但 remove() 队列为空时会抛异常。
}
}