1. 算法介绍
所谓多源，就是有多个起点。对应上一篇文章【BFS_最短路问题】的单源问题。这篇文章介绍用bfs解决边权为1(或边权相等)的多源最短路问题。
我们解决单源问题时，是先把起点入队列，再一层一层向外扩展。而多源问题是：把所有源点当成一个"超级源点"，把"超级源点"加入到队列，再一层一层向外扩展，就变成单源问题了。
如何把所有源点当成"超级源点"？
通过介绍下面的四道题目将给出答案。
2. 算法原理和代码实现
542.01矩阵
算法原理：
解法一：暴力求解。每个位置都用一次bfs计算出到最近0的距离，这毫无疑问会超时。
解法二：多源bfs+正难则反。
把所有的0当成起点，1当成终点。先把所有的0位置加入到队列中，再一层一层扩展即可。同时要创建一个与原矩阵等规模的dist矩阵，用来记录距离。
细节/技巧问题：
我们可以回想一下在解决单源最短路问题时，我们定义了一个bool类型的数组vis用来标记该位置是否被遍历过，最少步数step表示扩展层数，每次出队列的个数sz。
但是在这个问题中，我们创建的dist矩阵完全可以代替这三个东西，首先把dist矩阵初始化为-1，当dist矩阵的某一位置等于-1，说明原矩阵mat的对应位置没有标记过，当dist的某一位置不为-1，此时该位置记录的就是最近距离，并且原矩阵mat的对应位置标记过。
对于step和sz变量的作用，dist也可以代替。因为我们是从坐标[a, b] – > [x,y]进行搜索的，而dist[a,b]记录的等同于就是对应的层数。
代码实现：
class Solution
{
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
int m = mat.size(), n = mat[0].size();
// dist[i][j] == -1：mat[i][j]位置没有标记过
// dist[i][j] ！= -1：最短路
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
// 把0源点入队列
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;
}
while(q.size())
{
auto[a, b] = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
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;
}
};
当然，也可以使用"土方法"解决，这里也给出代码：
class Solution
{
int m, n;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
m = mat.size(), n = mat[0].size();
vector<vector<int>> dist(m, vector<int>(n)); // 距离矩阵
vector<vector<bool>> vis(m, vector<bool>(n)); // 标记矩阵
queue<pair<int, int>> q;
// 把所有的0入队列
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;
}
}
}
int step = 0;
while (q.size())
{
step++;
int sz = q.size();
while (sz--)
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y])
{
dist[x][y] = step;
q.push({ x, y });
vis[x][y] = true;
}
}
}
}
return dist;
}
};
1020.飞地的数量
算法原理：
这道题目可以抽象成多源bfs问题。不直接统计有多少被包围的陆地，正难则反，我们从边界上的陆地(1)做突破口。把所有边界上的1都入队列，再使用多源bfs进行搜索标记，最后再遍历一遍原数组，统计出没有标记的陆地数量即可。
细节/技巧问题：
参考前文
代码实现：
class Solution
{
bool vis[501][501];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
int numEnclaves(vector<vector<int>>& grid)
{
queue<pair<int, int>> q;
// 把所有边界上的1入队列
int m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i++)
{
if(grid[i][0] == 1) q.push({i, 0}), vis[i][0] = true;
if(grid[i][n-1] == 1) q.push({i, n-1}),vis[i][n-1] = true;
}
for(int j = 0; j < n; j++)
{
if(grid[0][j] == 1) q.push({0, j}), vis[0][j] = true;
if(grid[m-1][j] == 1) q.push({m-1, j}), vis[m-1][j] = true;
}
// 用多源bfs进行搜索标记
while(q.size())
{
auto[a,b] = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int x = a+dx[k], y = b+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
{
q.push({x, y});
vis[x][y] = 2;
}
}
}
// 最后遍历原矩阵，根据标记数组，统计陆地数量
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;
}
};
1765.地图中的最高点
算法原理：
这道题完完全全就是第一题的变式题。本题只能根据水域高度推陆地高度，所以可以使用多源bfs把所有水域位置当成"超级源点"入队列，再一层一层向外扩展。代码的实现也几乎一模一样。
细节/技巧问题：
参考第一题
代码实现：
class Solution
{
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
{
int m = isWater.size(), n = isWater[0].size();
vector<vector<bool>> vis(m, vector<bool>(n)); // 标记矩阵
vector<vector<int>> hight(m, vector<int>(n)); // 高度矩阵
queue<pair<int, int>> q;
// 把所有水域入队列，搞定置为0
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(isWater[i][j] == 1)
{
q.push({i, j});
vis[i][j] = true;
hight[i][j] = 0; // 水域的高度为0
}
// 使用多源bfs进行标记统计
while(q.size())
{
auto[a, b] = q.front();
q.pop();
for(int k = 0; k < 4 ; k++)
{
int x = a+dx[k], y = b+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y])
{
hight[x][y] = hight[a][b] + 1;
q.push({x, y});
vis[x][y] = true;
}
}
}
return hight;
}
};
1162.地图分析
算法原理：
这道题也是第一题的变式题。我们把所有的陆地看成起点入队列，再使用多源bfs向外一层一层扩展。
细节/技巧问题：
参考第一题
代码实现：
class Solution
{
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
int maxDistance(vector<vector<int>>& grid)
{
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for(int i = 0; i < m; i++)
for(int j= 0; j < n; j++)
if(grid[i][j] == 1)
{
// 所以陆地入队列，距离是0
q.push({i, j});
dist[i][j] = 0;
}
int ret = -1;
while(q.size())
{
auto[a, b] = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int x = a+dx[k], y = b+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
q.push({x, y});
dist[x][y] = dist[a][b] + 1;
ret = max(ret, dist[x][y]); // 更新出最大结果
}
}
}
return ret;
// 下面是另一种更新出最大值的方式
//int ret = 0;
//int sum = 0;
//for(int i = 0; i < m; i++)
// for(int j = 0; j < n; j++)
// {
// sum += dist[i][j];
// if(dist[i][j] >= ret)
// ret = dist[i][j];
// }
//return (sum == 0 || sum == -m*n) ? -1 : ret;
}
};
3. 算法总结
其实本篇文章的多源最短路和上一篇文章的单源最短路的思想基本上是一模一样的。无非一个是单起点一个是多起点，单起点就把那一个起点入队列就好了，而多起点就看成一个"超级源点"同时入队列就好了。如何把多个起点看成一个"超级源点"是关键，这就要根据题目具体分析了。