【ps】本篇有 4 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）01 矩阵
.1- 题目解析
.2- 代码编写
2）飞地的数量
.1- 题目解析
.2- 代码编写
3）地图中的最高点
.1- 题目解析
.2- 代码编写
4）地图分析
.1- 题目解析
.2- 代码编写
一、算法简介
最短路问题是图论中一种经典的题型，包括单源最短路、多源最短路、边权为 1 的最短路等等。本篇主要讲述的是边权为 1 的多源最短路问题。
简单来说，边权为 1 的单源最短路问题即为：求从单个起点到终点的最短路径距离，而边权为 1 的多源最短路问题即为：求从多个起点到终点的最短路径距离。
对于多源的最短路问题，我们将多个相邻的起点看作是一个整体，进而简化成一个起点，将多源转化成单源并利用 BFS 来处理，具体的方式是，在用队列进行 BFS 时，将所有起点入队，然后一层一层向外扩展。
二、相关例题
1）01 矩阵
542. 01 矩阵
.1- 题目解析
我们可以选择正难则反，不将 1 作为起点，而将 0 作为起点进行多源 BFS，去看 0 到达每个 1 的距离，从而得出最终的结果矩阵。
可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。在遍历的时候还需要标记一下处理过的 1 ，这样才能做到只遍历整个矩阵一次，具体的方式是，在创建结果矩阵之初，将矩阵元素的值全都初始化为 -1。
.2- 代码编写
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();vector<vector<int>> dist(m,vector<int>(n,-1));//dist[i][j]==-1,表示没有被搜索过//dist[i][j]!=-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;}}}//BFS向外扩展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){dist[x][y]=dist[a][b]+1;//每向外扩展一次，就相当于向外走了一步q.push({x,y});}}}return dist;}
};2）飞地的数量
1020. 飞地的数量
.1- 题目解析
与上道题类似，我们也可以正难则反，从矩阵边上的 1 开始搜索，把与这些 1 相连的区域全部标记一下，然后再遍历一遍矩阵，统计哪些位置的 1 没有被标记即可，这些没有被标记的 1 就是不能到达边界的陆地。
.2- 代码编写
class Solution {int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:int numEnclaves(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();vector<vector<bool>> vis(m,vector<bool>(n));//标记某位置是否已经搜索过queue<pair<int,int>> q;//将矩阵边缘的 1 全部入队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){q.push({i,j});vis[i][j]=true;}}}}//进行bfs向外扩展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 && grid[x][y]==1 && !vis[x][y]){vis[x][y]=true;q.push({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）地图中的最高点
1765. 地图中的最高点
.1- 题目解析
本题类似于上文的《01矩阵》，也可以选择正难则反，以水域为起点，通过 BFS 向外扩展来安排结果矩阵中每个元素的高度，使得结果矩阵中的高度（元素）之和最大。
.2- 代码编写
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<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(isWater[i][j]){dist[i][j]=0;q.push({i,j});}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){dist[x][y]=dist[a][b]+1;q.push({x,y});}}}return dist;}
};4）地图分析
1162. 地图分析
.1- 题目解析
本题类似于上文的《01矩阵》，曼哈顿距离其实就是最短距离，于是也可以选择正难则反，以陆地为起点，通过 BFS 向海洋去扩展。
.2- 代码编写
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]){dist[i][j]=0;q.push({i,j});}int ret=-1;//统计最大的结果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){dist[x][y]=dist[a][b]+1;q.push({x,y});ret=max(ret,dist[x][y]);//统计结果}}}return ret;}
};