題目
#

題目簡述
#

給定一個由 0 和 1 組成的矩陣，返回一個相同大小的矩陣，其中每個元素表示該位置到最近的 0 的距離。

範例
#

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Explanation: 每個 1 到最近的 0 的距離分別為 1，其餘為 0。

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation: 每個 1 到最近的 0 的距離分別為 1 或 2。

___

解題思路
#

這題要求我們找到矩陣中每個元素到最近的 0 的距離。對於每個元素，我們需要計算它到最近的 0 的曼哈頓距離。

我們可以從所有的 0 開始，向外擴展，逐層計算距離。

解法
#

使用BFS來解決：

首先將所有 0 的位置加入隊列，並標記為已訪問。
使用 BFS 從所有 0 開始向外擴展。
對於每個位置，檢查四個方向（上下左右）的相鄰位置。
如果相鄰位置未訪問過，則將其加入隊列，並設置距離為當前層數。

例子說明
#

mat = [[0,0,0],[0,1,0],[1,1,1]]

初始情況：所有 0 的位置加入隊列，queue = [(0,0), (0,1), (0,2), (1,0), (1,2)]

第一層（距離 = 0）：
- 處理所有 0 的位置：(0,0), (0,1), (0,2), (1,0), (1,2)
- 將相鄰的 1 加入隊列：(1,1), (2,0), (2,2)
第二層（距離 = 1）：
- 處理 (1,1), (2,0), (2,2)
- 將相鄰的 1 加入隊列：(2,1)
第三層（距離 = 2）：
- 處理 (2,1)
- 沒有新的相鄰位置
最終結果：
- [[0,0,0],[0,1,0],[1,2,1]]

完整程式碼
#

java

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

class Solution {
    // 定義四個方向的移動：右、左、下、上
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] res = new int[m][n]; // 結果矩陣，存儲每個位置到最近0的距離
        boolean[][] visited = new boolean[m][n]; // 訪問標記矩陣，避免重複訪問
        Queue<int[]> queue = new LinkedList<>(); // BFS 隊列，存儲待處理的位置
        
        // 將所有 0 的位置加入隊列，並標記為已訪問
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j}); // 將0的位置加入隊列
                    visited[i][j] = true; // 標記為已訪問
                }
            }
        }

        int cost = 0; // 當前層的距離
        while (!queue.isEmpty()) { // 當隊列不為空時繼續處理
            int size = queue.size(); // 當前層的節點數量

            // 處理當前層的所有節點
            for (int s = 0; s < size; s++) {
                int[] cur = queue.poll(); // 取出隊首節點
                int x = cur[0], y = cur[1]; // 獲取節點的座標
                
                // 如果當前位置是 1，設置其距離為當前層數
                if (mat[x][y] == 1) {
                    res[x][y] = cost; // 設置距離
                }

                // 檢查四個方向的相鄰位置
                for (int[] dir : dirs) {
                    int i = x + dir[0], j = y + dir[1]; // 計算相鄰位置的座標
                    // 確保位置在矩陣範圍內且未訪問過
                    if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]) {
                        queue.offer(new int[]{i, j}); // 將相鄰位置加入隊列
                        visited[i][j] = true; // 標記為已訪問
                    }
                }
            }
            cost++; // 進入下一層，距離加 1
        }

        return res; // 返回結果矩陣
    }
}