多源最短路径

---

1. 01 矩阵（542）

题目描述：

算法原理：
这题会想到能不能遍历每一个格子中的元素，然后挨个的去进行单源最短路径的操作，但是题目中指出要得到的矩阵是每个格子中的元素到最近的0的距离，那么我们完全可以从矩阵中的0出发，设置距离的矩阵，以一种类似于FloodFill算法的方法来更新记录从0走了多少步的距离矩阵，具体看代码。
代码如下：

class Solution {public int[][] updateMatrix(int[][] mat) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = mat.length;int n = mat[0].length;int[][] dis = new int[m][n];Queue<int[]> q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (mat[i][j] == 0) {dis[i][j] = 0;q.add(new int[] { i, j });} else {dis[i][j] = -1;}}}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1) {dis[x][y] = dis[a][b] + 1;q.add(new int[] { x, y });}}}return dis;}
}

题目链接

2. 飞地的数量（1020）

题目描述：

算法原理：
和上题思想类似，上题是从终点0出发，这题是从终点的边界1元素出发去不断的发散，直至队列为空，此时还没有被遍历到的元素1就是走不出去的。
代码如下：

class Solution {public int numEnclaves(int[][] grid) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = grid.length, n = grid[0].length;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 (i == 0 || i == m - 1 || j == 0 || j == n - 1) {if (grid[i][j] == 1) {vis[i][j] = true;queue.add(new int[] { i, j });}}}}while (!queue.isEmpty()) {int[] temp = queue.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) {vis[x][y] = true;queue.add(new int[] { x, y });}}}int ret = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1 && !vis[i][j]) {ret++;}}}return ret;}
}

题目链接

3. 地图分析（1162）

题目描述：

算法原理：
这题就是第一题的换一种问法，做法和第一题一致。
代码如下：

class Solution {public int maxDistance(int[][] grid) {int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int m = grid.length;int n = grid[0].length;int[][] dis = new int[m][n];Queue<int[]> q = new LinkedList<>();boolean flg1 = false;boolean flg2 = false;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dis[i][j] = -1;}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {flg1 = true;q.add(new int[] { i, j });dis[i][j] = 0;} else {flg2 = true;}}}if (!(flg1 && flg2)) {return -1;}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1) {dis[x][y] = dis[a][b] + 1;q.add(new int[] { x, y });}}}int ret = Integer.MIN_VALUE;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {ret = Math.max(ret, dis[i][j]);}}}return ret;}
}

题目链接

4. 地图中的最高点（1765）

题目描述：

算法原理：
做法同前三题类似，但是就是需要意识到前面的做法就能够得到最高，因为我们从水域开始周围的高度完全可以赋为0但是我们用了一个小贪心就是每次高度差都是1体现在我们代码中就是类似于前面的距离+1。
代码如下：

class Solution {public int[][] highestPeak(int[][] isWater) {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m = isWater.length;int n = isWater[0].length;int[][] ret = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {ret[i][j] = -1;}}Queue<int[]> q = new LinkedList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (isWater[i][j] == 1) {q.add(new int[] { i, j });ret[i][j] = 0;}}}while (!q.isEmpty()) {int[] temp = q.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1) {ret[x][y] = ret[a][b] + 1;q.add(new int[] { x, y });}}}return ret;}
}

题目链接