.net 电子商务网站源码,开网站做网站赚钱吗,wordpress 评论模板,网页设计代码及图片1.单源最短路问题
一个起点一个终点。
定义#xff1a;在给定加权图中#xff0c;选择一个顶点作为源点#xff0c;计算该源点到图中所有其他顶点的最短路径长度。
2.多源最短路问题
定义#xff1a;多源最短路问题指的是在图中存在多个起点#xff0c;需要求出从这些…1.单源最短路问题
一个起点一个终点。
定义在给定加权图中选择一个顶点作为源点计算该源点到图中所有其他顶点的最短路径长度。
2.多源最短路问题
定义多源最短路问题指的是在图中存在多个起点需要求出从这些起点到图中所有其他顶点的最短路径。
3.多源BFS
用BFS解决边权为1的多源最短路问题。
解法一: 暴力解法把多源最短路问题转化为若干个单源最短路问题。
解法二 把所有的源点变成一个“超级源点”问题就变成了单一的单源最短路问题。
把所有的起点加入到队列里面。一层一层的往外扩展。
4.例题
4.1 01 矩阵 给定一个由 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]]解法(bfs)(多个源头的最短路问题) 算法思路: 对于求的最终结果我们有两种方式: 第一种方式:从每一个 1开始然后通过层序遍历找到离它最近的0。 这一种方式我们会以所有的 1 起点来一次层序遍历势必会遍历到很多重复的点。并且如果矩阵中只有一个 0 的话每一次层序遍历都要遍历很多层时间复杂度较高。 换一种方式:从 0开始层序遍历并且记录遍历的层数。当第一次碰到1的时候当前的层数就是这个 1 离 0 的最短距离。 这一种方式我们在遍历的时候标记一下处理过的 1能够做到只用遍历整个矩阵一次就能得到最终结果。 但是这里有一个问题0是有很多个的我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢? 其实很简单我们可以先把所有的 0 都放在队列中把它们当成一个整体每次把当前队列里面的所有元素向外扩展一次。
class Solution {typedef pairint,int PII;int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};
public:vectorvectorint updateMatrix(vectorvectorint mat) {queuePII qe;int mmat.size();int nmat[0].size();//vv[i][j]-1 表示没有搜索过//vv[i][j]!-1 表示最短距离vectorvectorint vv(m,vectorint(n,-1));//把所有的源点加入队列for(int i0;im;i){for(int j0;jn;j){if(mat[i][j]0){qe.push({i,j});vv[i][j]0;}}}//一层一层往外扩展while(qe.size()){auto [a,b]qe.front();qe.pop();for(int k0;k4;k){int xadx[k];int ybdy[k];if(x0xmy0ynvv[x][y]-1){vv[x][y]vv[a][b]1;qe.push({x,y});}}}return vv;}
};
4.2 飞地的数量 给你一个大小为 m x n 的二进制矩阵 grid 其中 0 表示一个海洋单元格、1 表示一个陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻上、下、左、右的陆地单元格或跨过 grid 的边界。 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。 示例 1 输入grid [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出3
解释有三个 1 被 0 包围。一个 1 没有被包围因为它在边界上。示例 2 输入grid [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出0
解释所有 1 都在边界上或可以到达边界。 解法: 算法思路: 正难则反: 从边上的 1开始搜索把与边上1相连的联通区域全部标记一下 然后再遍历一遍矩阵看看哪些位置的1没有被标记即可。 标记的时候可以用「多源 bfs」解决。
class Solution {typedef pairint,int PII;int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};
public:int numEnclaves(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();queuePII qe;vectorvectorbool vv(m,vectorbool(n,false));//将边上的1加入到队列中for(int i0;im;i){if(grid[i][0]1)qe.push({i,0});if(grid[i][n-1]1)qe.push({i,n-1});}for(int j0;jn;j){if(grid[0][j]1)qe.push({0,j});if(grid[m-1][j]1)qe.push({m-1,j});}while(qe.size()){auto [a,b]qe.front();qe.pop();vv[a][b]true;for(int k0;k4;k){int xadx[k];int ybdy[k];if(x0xmy0yn!vv[x][y]grid[x][y]1){qe.push({x,y});vv[x][y]true;}}}int count0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1vv[i][j]false)count;}}return count;}
};
4.3 地图中的最高点 给你一个大小为 m x n 的整数矩阵 isWater 它代表了一个由 陆地 和 水域 单元格组成的地图。 如果 isWater[i][j] 0 格子 (i, j) 是一个 陆地 格子。如果 isWater[i][j] 1 格子 (i, j) 是一个 水域 格子。 你需要按照如下规则给每个单元格安排高度 每个格子的高度都必须是非负的。如果一个格子是 水域 那么它的高度必须为 0 。任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着就称它们为相邻的格子。也就是说它们有一条公共边 找到一种安排高度的方案使得矩阵中的最高高度值 最大 。 请你返回一个大小为 m x n 的整数矩阵 height 其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法请返回 任意一个 。 示例 1 输入isWater [[0,1],[0,0]]
输出[[1,0],[2,1]]
解释上图展示了给各个格子安排的高度。
蓝色格子是水域格绿色格子是陆地格。示例 2 输入isWater [[0,0,1],[1,0,0],[0,0,0]]
输出[[1,1,0],[0,1,1],[1,2,2]]
解释所有安排方案中最高可行高度为 2 。
任意安排方案中只要最高高度为 2 且符合上述规则的都为可行方案。 解法直接使用多源BFS。
class Solution {typedef pairint,int PII;int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};
public:vectorvectorint highestPeak(vectorvectorint isWater) {int misWater.size();int nisWater[0].size();vectorvectorint vv(m,vectorint(n,-1));queuePII qe;//把所有的源点加入队列中for(int i0;im;i){for(int j0;jn;j){if(isWater[i][j]1){vv[i][j]0;qe.push({i,j});}}}while(qe.size()){auto [a,b]qe.front();qe.pop();for(int k0;k4;k){int xadx[k];int ybdy[k];if(x0xmy0ynvv[x][y]-1){qe.push({x,y});vv[x][y]vv[a][b]1;}}}return vv;}
}; 4.4 地图分析 你现在手里有一份大小为 n x n 的 网格 grid上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋1 代表陆地。 请你找出一个海洋单元格这个海洋单元格到离它最近的陆地单元格的距离是最大的并返回该距离。如果网格上只有陆地或者海洋请返回 -1。 我们这里说的距离是「曼哈顿距离」 Manhattan Distance(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| |y0 - y1| 。 示例 1 输入grid [[1,0,1],[0,0,0],[1,0,1]]
输出2
解释
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大最大距离为 2。示例 2 输入grid [[1,0,0],[0,0,0],[0,0,0]]
输出4
解释
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大最大距离为 4。解法01矩阵的变形题直接上多源BFS。
class Solution {typedef pairint,int PII;int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};
public:int maxDistance(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();queuePII qe;vectorvectorint vv(m,vectorint(n,-1));for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1){vv[i][j]0;qe.push({i,j});}}}while(qe.size()){auto [a,b]qe.front();qe.pop();for(int k0;k4;k){int xadx[k];int ybdy[k];if(x0xmy0ynvv[x][y]-1){qe.push({x,y});vv[x][y]vv[a][b]1;}}}int ret0;for(int i0;im;i){for(int j0;jn;j){retmax(ret,vv[i][j]);}}if(ret0)return -1;return ret;}
};
