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 設為 -1for (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 設為 -1for (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()); // 10System.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()); // 10System.out.println("出隊元素：" + pq.poll()); // 20//queue.poll() 與 remove() 類似，但 remove() 隊列為空時會拋異常。}
}
)
