描述

給定一個由0和1組成的矩陣，求每個單元格最近的0的距離。
兩個相鄰細胞之間的距離是1。

給定矩陣的元素數不超過10,000。
在給定的矩陣中至少有一個0。
單元格在四個方向上相鄰:上，下，左和右。

樣例

例1:

輸入:
[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]]
輸出:
[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0]]

例2:

輸入:
[[0,1,0,1,1],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]
輸出:
[[0,1,0,1,2],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]

本題主要考察廣度優先搜索??

如需更快更簡潔的算法請跳至思路2

思路1:?

思路1雖然也是廣度優先搜索算法 但是是單源的廣度優先搜索算法 即逐個繼續遍歷擴展其周圍的元素

外層循環為每一層,內層循環為每一層的當前輸入值

然后通過兩個變量 path來記錄路徑的長度 隊列來記錄為未滿足為0的位置索引 每次判斷但凡隊列的點相鄰但凡沒有一個符合條件就先讓path+1 ?

然后記錄所有不符合的點 直至循環出相鄰有0的點 因為題目已經告知給定的矩陣至少有一個0

這就是每一個元素的遍歷

最后將所有元素都這樣執行一遍就可以得到每一個單元距離0的距離

即簡要理解為針對每個 1 向外找最近 0

代碼如下:

import java.util.*;

public class Solution {

? ? /**

? ? ?* @param matrix: a 0-1 matrix

? ? ?* @return: return a matrix

? ? ?*/

? ? public int[][] updateMatrix(int[][] matrix) {

? ? ? ? int m = matrix.length;

? ? ? ? int n = matrix[0].length;

? ? ? ? int[][] pathMatrix = new int[m][n]; // 最終結果矩陣

? ? ? ? int path; // 當前單元格的路徑

? ? ? ? Queue<int[]> integerQueue = new LinkedList<>(); // 存坐標的隊列

? ? ? ? // 遍歷每個單元格

? ? ? ? for (int i = 0; i < m; i++) {

? ? ? ? ? ? for (int j = 0; j < n; j++) {

? ? ? ? ? ? ? ? if (matrix[i][j] == 0) {

? ? ? ? ? ? ? ? ? ? pathMatrix[i][j] = 0;

? ? ? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? ? ? // BFS 查找最近的 0

? ? ? ? ? ? ? ? ? ? boolean[][] visited = new boolean[m][n];

? ? ? ? ? ? ? ? ? ? integerQueue.clear();

? ? ? ? ? ? ? ? ? ? integerQueue.offer(new int[]{i, j});

? ? ? ? ? ? ? ? ? ? visited[i][j] = true;

? ? ? ? ? ? ? ? ? ? path = 0;

? ? ? ? ? ? ? ? ? ? boolean found = false;

? ? ? ? ? ? ? ? ? ? while (!integerQueue.isEmpty() && !found) {

? ? ? ? ? ? ? ? ? ? ? ? int size = integerQueue.size();

? ? ? ? ? ? ? ? ? ? ? ? path++; // 每擴展一層，路徑 +1

? ? ? ? ? ? ? ? ? ? ? ? for (int q = 0; q < size; q++) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? int[] pos = integerQueue.poll();

? ? ? ? ? ? ? ? ? ? ? ? ? ? int x = pos[0];

? ? ? ? ? ? ? ? ? ? ? ? ? ? int y = pos[1];

? ? ? ? ? ? ? ? ? ? ? ? ? ? int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右

? ? ? ? ? ? ? ? ? ? ? ? ? ? for (int[] dir : dirs) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int nx = x + dir[0];

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int ny = y + dir[1];

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (matrix[nx][ny] == 0) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? pathMatrix[i][j] = path;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? found = true;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? integerQueue.offer(new int[]{nx, ny});

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? visited[nx][ny] = true;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? ? ? if (found) break;

? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return pathMatrix;

? ? }

}

時間復雜度為:O(m × n)^2

思路2:多源廣度優先算法

同時從多個起點出發進行 BFS，也就是說：
不是一個一個來，而是全部起點一起“向外一層層擴散”

即所有 0 一起擴散? 訪問一次就是最短路徑 無冗余訪問 即類似于同步水波擴散

需要注意的是?

m代表的是行數

n代表的是列數

代碼如下:

public class Solution {

? ? public int[][] updateMatrix(int[][] matrix) {

? ? ? ? int m = matrix.length;

? ? ? ? int n = matrix[0].length;

? ? ? ? int[][] pathMatrix = new int[m][n];

? ? ? ? boolean[][] visited = new boolean[m][n];

? ? ? ? Queue<int[]> integerQueue = new LinkedList<>();

? ? ? ? //注意這里用LinkList 因為效率高 入隊出隊都是O(1) 而且LinkList實現了Deque,Deque又繼承了隊列,所以Queue可以直接用其實現類 LinkList.

? ? ? ? // 將所有為0的點入隊，作為BFS的起點

? ? ? ? for (int y = 0; y < m; y++) {

? ? ? ? ? ? for (int x = 0; x < n; x++) {

? ? ? ? ? ? ? ? if (matrix[y][x] == 0) {

? ? ? ? ? ? ? ? ? ? integerQueue.offer(new int[]{y, x});

? ? ? ? ? ? ? ? ? ? visited[y][x] = true;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? // 上下左右

? ? ? ? int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

? ? ? ? while (!integerQueue.isEmpty()) {

? ? ? ? ? ? int[] point = integerQueue.poll();

? ? ? ? ? ? int y = point[0], x = point[1];

? ? ? ? ? ? for (int[] dir : directions) {

? ? ? ? ? ? ? ? int newY = y + dir[0];

? ? ? ? ? ? ? ? int newX = x + dir[1];

? ? ? ? ? ? ? ? if (newY >= 0 && newY < m && newX >= 0 && newX < n && !visited[newY][newX]) {

? ? ? ? ? ? ? ? ? ? pathMatrix[newY][newX] = pathMatrix[y][x] + 1;

? ? ? ? ? ? ? ? ? ? visited[newY][newX] = true;

? ? ? ? ? ? ? ? ? ? integerQueue.offer(new int[]{newY, newX});

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return pathMatrix;

? ? }

}

?