兼职网站平台有哪些_百度快照不更新_seo网络推广报价_黑帽seo技术论坛

---

0. 多源最短路问题介绍

---

如图，红色是出发点，蓝色是终点。以前我们做的题中，出发点只有一个，所谓多源的意思就是，出发点有多个，求最短路径。

当然，这种题的解题思路就是，将所有的出发点，合在一起，变成一个超级源点，直接计算从这个超级源点出发，到目标点的最短距离即可。

---

1. 题目解析+算法分析

---

leetcode链接：https://leetcode.cn/problems/2bCMpM/description/

1. 题目解析

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

• 示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

• 示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

2. 算法分析

• 我们可以将所有的0先入队列，这一步是形成超级源点的一步。然后开始bfs向外搜索。

---

2. 代码实现

---

1. 版本1：vis数组版

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {m = mat.size(), n = mat[0].size();bool vis[m][n];// 1. 将所有的源点0入队queue<pair<int, int>> q;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (mat[i][j] == 0) {q.push({i, j});vis[i][j] = true;}else{vis[i][j] = false;}}}// 2. 开始搜索int count = 0;while (q.size()){count++;int sz = q.size();while (sz--){auto [a, b] = q.front();q.pop();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 && mat[x][y] && !vis[x][y]){mat[x][y] = count;q.push({x, y});vis[x][y] = true;}}}}return mat;}
};

2. 版本2：dist数组版

• 版本1中，我们需要用一个vis数组，记录每个节点有没有被访问过，还要用一个变量sz，来实现一层一层向外扩展的动作。并且需要一个变量count记录步数。
• 上面这三个动作，都可以通过一个dist数组实现，它的实际意义是记录每个位置离源点的距离。
  • dist数组初始化为-1，表示该位置没有被访问过；
  • dist数组值不为-1，表示搜索过了，且当前的值为遍历层数。

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {m = mat.size(), n = mat[0].size();// dist[i][j] == -1 表示：没有被搜索过// dist[i][j] != -1 表示：搜索过了，且值为最短路径vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;// 1. 将所有的源点加入到队列中for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (mat[i][j] == 0){q.push({i, j});dist[i][j] = 0;}}}// 2. 一层一层向外扩展while(q.size()){auto [a, b] = q.front();q.pop();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 && dist[x][y] == -1){q.push({x, y});dist[x][y] = dist[a][b] + 1;}}}return dist;}
};

---