542.01矩陣
題目鏈接：542. 01 Matrix
開始我的思路是找每個(gè)1然后廣度優(yōu)先遍歷直到找到0的距離肛根，發(fā)現(xiàn)這種方法難以實(shí)現(xiàn)且晦澀。看了大神的題解才明白狼荞，使用廣度優(yōu)先搜索需要從0開始，一層一層往外尋找帮碰。
_ _ _ _ _ 1 _ _ 2 1 2 _ 2 1 2 3 2 1 2 3
_ 0 _ _ ==> 1 0 1 _ ==> 1 0 1 2 ==> 1 0 1 2 ==> 1 0 1 2
_ _ _ _ _ 1 _ _ 2 1 2 _ 2 1 2 3 2 1 2 3
_ _ _ _ _ _ _ _ _ 2 _ _ 3 2 3 _ 3 2 3 4
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
我們把全部的0入隊(duì)相味，并且把原來的1置為-1（說明沒有被訪問過），然后出隊(duì)殉挽，如果周圍有-1丰涉，則距離就是出隊(duì)的元素的數(shù)值+1
代碼：
class Solution {
public int[][] updateMatrix(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
Deque<int[]> deque = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == 0) //把所有0入隊(duì)
deque.offer(new int[]{i, j});
if (matrix[i][j] == 1)
matrix[i][j] = -1; //把1都置為-1,表示沒有訪問過
}
}
int[] xPos = new int[]{0, 0, 1, -1};
int[] yPos = new int[]{-1, 1, 0, 0};
while (!deque.isEmpty()) {
int[] pos = deque.poll();
for (int i = 0; i < 4; i++) {
int x = pos[0] + xPos[i];
int y = pos[1] + yPos[i];
if (x >= 0 && x < N && y >= 0 && y < M && matrix[x][y] == -1) {
//每個(gè)出隊(duì)元素只訪問其上下左右四個(gè)方向
matrix[x][y] = matrix[pos[0]][pos[1]] + 1;
deque.offer(new int[]{x, y}); //改變了后入隊(duì),檢查其上下左右
}
}
}
return matrix;
}
}
