![01 矩阵-542-[中等]](http://www.mshxw.com/aiimages/31/781435.png "01 矩阵-542-[中等]")
力扣https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
方法一：广度优先搜索思考
- 如果按照模板代码逻辑对元素逐个BFS搜索，思路没问题，但是有很多重复计算，运行超时所以反过来从所有的０开始搜索
- 搜索０的时候还必须满足是和１挨着的０才行这样所有和０挨着的１都直接算出了距离然后和１挨着的１可以通过递归公式算出距离：ｄ［ｘ］＋１＝ｄ［ｘ＋１］递推公式很关键BFS的起点很关键，不能直接暴力每个元素开始访问过的元素需要有去重过滤数组边界考虑是基础
熟悉「最短路」的读者应该知道，我们所说的「超级零」实际上就是一个「超级源点」。在最短路问题中，如果我们要求多个源点出发的最短路时，一般我们都会建立一个「超级源点」连向所有的源点，用「超级源点」到终点的最短路等价多个源点到终点的最短路。
package com.company.myQueue;
import java.util.linkedList;
import java.util.Queue;
public class Solution13_1 {
//首先把每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ）
public int[][] updateMatrix(int[][] matrix) {
int[] dx = new int[]{-1, 1, 0, 0};
int[] dy = new int[]{0, 0, -1, 1};
Queue queue = new linkedList<>();
int m = matrix.length;
int n = matrix[0].length;
int[][] result = new int[m][n];
//两层循环遍历每个元素
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
//遇到等于0的元素,将所有0元素入队
if (matrix[i][j] == 0) {
//访问等于0的元素的上下左右的邻接点
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
//数组边界判断 x,y
//matrix[x][y] == 1 上下左右的邻接点必须等于的元素1才考虑，如果邻接点等于0就跳过
//result[x][y] == 0 当前顶点还没计算过距离还是初始值0，防止重复计算
if (x >= 0
&& x < m
&& y >= 0
&& y < n
&& matrix[x][y] == 1
&& result[x][y] == 0) {
//入队后就表示计算过，result[x][y] = 1，因为0是和(x,y)挨着的，所有距离都是固定的1
result[x][y] = 1;
//入队
queue.offer(new int[]{x, y});
}
}
}
}
}
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0], y = point[1];
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
//matrix[newX][newY] == 1 队列中的元素目前都是1，再次校验一下
//result[newX][newY] == 0 new节点还没计算过距离
if (newX >= 0
&& newX < m
&& newY >= 0
&& newY < n
&& matrix[newX][newY] == 1
&& result[newX][newY] == 0) {
result[newX][newY] = result[x][y] + 1;
queue.offer(new int[]{newX, newY});
}
}
}
return result;
}
}
BFS暴力搜索超时的版本
当元素中只有一个0或少量的0元素时，就会运行超时一个用例没过，就是只有一个0的场景对比看理解更深刻
package com.company.myQueue;
import java.util.*;
public class Solution13 {
public static void main(String[] args) {
int[][] mat = new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
new Solution13().updateMatrix(mat);
}
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
result[i][j] = 0;
} else {
bfs(mat, i, j, result);
}
}
}
return result;
}
private int bfs(int[][] mat, int i, int j, int[][] result) {
ArrayDeque> queue = new ArrayDeque<>();
Set visited = new HashSet<>();
List root = new ArrayList<>();
root.add(0, i);
root.add(1, j);
root.add(2, 0);
queue.offer(root);
visited.add(i + "_" + j);
int count = 0;
while (!queue.isEmpty()) {
List cur = queue.pop();
int curI = cur.get(0);
int curJ = cur.get(1);
int times = cur.get(2);
if (curI >= 0
&& curJ >= 0
&& curI < mat.length
&& curJ < mat[0].length) {
if (mat[curI][curJ] == 0) {
result[i][j] = times;
break;
} else {
count++;
}
int upI = curI - 1;
int upJ = curJ;
List up = new ArrayList<>();
up.add(0, upI);
up.add(1, upJ);
up.add(2, times + 1);
if (!visited.contains(upI + "_" + upJ)) {
queue.offer(up);
visited.add(upI + "_" + upJ);
}
int downI = curI + 1;
int downJ = curJ;
List down = new ArrayList<>();
down.add(0, downI);
down.add(1, downJ);
down.add(2, times + 1);
if (!visited.contains(downI + "_" + downJ)) {
queue.offer(down);
visited.add(downI + "_" + downJ);
}
int leftI = curI;
int leftJ = curJ - 1;
List left = new ArrayList<>();
left.add(0, leftI);
left.add(1, leftJ);
left.add(2, times + 1);
if (!visited.contains(leftI + "_" + leftJ)) {
queue.offer(left);
visited.add(leftI + "_" + leftJ);
}
int rightI = curI;
int rightJ = curJ + 1;
List right = new ArrayList<>();
right.add(0, rightI);
right.add(1, rightJ);
right.add(2, times + 1);
if (!visited.contains(rightI + "_" + rightJ)) {
queue.offer(right);
visited.add(rightI + "_" + rightJ);
}
times++;
}
}
return count;
}
}
方法二：动态规划-1
力扣https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
方法二：动态规划-2
