[数据结构与算法]lc542.找出矩阵中每个元素到0的最短距离

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

BFS

假设这个矩阵中恰好只有一个 0，应该怎么做？由于矩阵中只有一个 0，那么对于每一个 1，离它最近的 0 就是那个唯一的 0。如何求出这个距离呢？
1）、如果0在矩阵中的位置是(i0, j0)，1在矩阵中的位置(i1, j1)，则距离为 |i0 - i1| + |j0 - j1|。
2）、从0的位置开始广度搜索，找到这个位置到其余所有点的 最短距离，因此如果我们从 0 开始搜索，每次搜索到一个 1，就可以得到 0 到这个 1 的最短距离，也就离这个 1 最近的 0 的距离了（因为矩阵中只有一个 0）。

上面的两种做法，第一种只需要对每一个位置计算一下就行；第二种需要实现广度优先搜索，会复杂一些。但是，题目中会有不止一个 0，这样以来，如果要使用第一种做法，就必须对于每个 1 计算一次它到所有的 0 的距离，再从中取一个最小值，时间复杂度会非常高。而对于第二种做法，我们可以很有效地处理有多个 0 的情况。
处理的方法很简单：我们在进行广度优先搜索的时候会使用到队列，在只有一个 0 的时候，我们在搜索前会把这个 0 的位置加入队列，才能开始进行搜索；如果有多个 0，我们只需要把这些 0 的位置都加入队列就行了。

这样做为什么是正确的呢？
**我们可以把这些 0 看成一个整体好了。我们可以添加一个「超级零」，它与矩阵中所有的 0 相连，这样的话，任意一个 1 到它最近的 0 的距离，会等于这个 1 到「超级零」的距离减去一。**由于我们只有一个「超级零」，我们就以它为起点进行广度优先搜索。这个「超级零」只和矩阵中的 0 相连，所以在广度优先搜索的第一步中，「超级零」会被弹出队列，而所有的 0 会被加入队列，它们到「超级零」的距离为 1。这就等价于：一开始我们就将所有的 0 加入队列，它们的初始距离为 0。这样以来，在广度优先搜索的过程中，我们每遇到一个 1，就得到了它到「超级零」的距离减去一，也就是 这个 1 到最近的 0 的距离。

代码

class Sloution{
	static int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	public int[][] updateMartix(int[][] matrix){
		int m = matrix.length, n = matrix[0].length;
		int[][] dist = new int[m][n];
		boolean vis = new boolean[m][n];
		Queue<int[]> queue = new LinkedList<>();
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(matrix[i][j] == 0){
					queue.offer(new int[]{i, j});
					vis[i][j] = true;
				}
			}
		}
		//广度优先搜索
		while(!queue.isEmpty()){
			int[] cell = queue.poll();
			int i = cell[0], j = cell[1];
			for(int d = 0; d < 4; d++){
				int ni = i + dirs[d][0];
				int nj = j + dirs[d][1];
				if(ni >= 0 && ni < m; && nj >=0 && nj < n && !vis[ni][nj]){
					dist[ni][nj] = dist[i][j] + 1;
					queue.offer(new int[]{ni, nj});
					vis[ni][nj] = true;
				}
			}
		}
		return dist;
	}
}