深圳网站设计价格表,富阳网站定制开发哪家公司好,建设银行违法网站,广告设计好找工作吗文章目录 多源BFS542. 01 矩阵题目解析算法原理代码实现 1020. 飞地的数量题目解析算法原理 1765. 地图中的最高点题目解析算法原理代码实现 1162. 地图分析题目解析算法原理代码实现 多源BFS
单源最短路#xff1a; 一个起点、一个终点
多源最短路#xff1a; 可以多个起点… 文章目录 多源BFS542. 01 矩阵题目解析算法原理代码实现 1020. 飞地的数量题目解析算法原理 1765. 地图中的最高点题目解析算法原理代码实现 1162. 地图分析题目解析算法原理代码实现 多源BFS
单源最短路 一个起点、一个终点
多源最短路 可以多个起点一个终点
多源BFS 用BFS解决边权为1的多源最短路 BFS 解决边权为1的最短路问题 如何解决
解法一暴力枚举把多源最短路转换成若干个单源最短路大概率超时解法二把所有源点当成一个“超级源点”问题就变成了单一的单源最短路问题 想办法将若干个起点当作一个起点
为什么正确 如图 如何代码实现
所有起点加入到队列当中一层一层向外扩展
542. 01 矩阵
题目链接542. 01 矩阵
题目解析
给我们一个矩阵矩阵由0和1组成
要我们返回的也是一个矩阵里面放的是每个位置里0最近的距离 算法原理
把所有的0当成起点1当成终点将所有0位置加入队列一层一层向外扩展 代码实现
class Solution {
public:int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};vectorvectorint updateMatrix(vectorvectorint mat){int m mat.size();int n mat[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, 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});dist[i][j] 0;}}}while(q.size()){auto [a, b] q.front();q.pop();for(int k 0; k 4; k){int x dx[k] a;int y dy[k] b;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;}
};1020. 飞地的数量
题目链接1020. 飞地的数量
题目解析
给我们一个矩阵由0和1组成1表示陆地0表示海洋
要我们求出无法“上岸”数量 算法原理
正难则反
直接看四个边界是否有“陆地”
如果有直接往里面搜索看有多少连在一起的
class Solution {
public:int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int numEnclaves(vectorvectorint grid){int m grid.size();int n grid[0].size();vectorvectorbool vis(m, vectorbool(n));queuepairint, int q;//四周 1 加入队列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;} }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;}}//多源bfswhile(q.size()){auto [a, b] q.front();q.pop();for(int k 0; k 4; k){int x dx[k] a;int y dy[k] b;if(x 0 y 0 x m 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;}
};1765. 地图中的最高点
题目链接1765. 地图中的最高点
题目解析
给我们一个矩阵由陆地和水域组成
isWater[i][j] 0为陆地isWater[i][j] 1为水域
规则如下
格子高度非负格子为水域高度为0相邻格子高度差不大于1
最终要得出怎么排列能得到让最高的高度最大。
算法原理
这里最先排列的肯定是水域如果是水域设置为0即先遍历矩阵将水域格子加入队列然后一层一层向外扩展 代码实现
class Solution {
public:int dx[4] {1, -1, 0, 0};int dy[4] {0, 0, 1, -1};vectorvectorint highestPeak(vectorvectorint isWater){int m isWater.size();int n isWater[0].size();vectorvectorint dist(m,vectorint(n, -1));queuepairint, int q;for(int i 0; i m; i){for(int j 0; j n; j){if(isWater[i][j] 1){dist[i][j] 0;q.push({i, j});}}}while(q.size()){auto [a, b] q.front();q.pop();for(int k 0; k 4; k){int x dx[k] a;int y dy[k] b;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;}
};1162. 地图分析
题目链接1162. 地图分析
题目解析
给我一个矩阵0和1组成
0表示海洋1表示陆地
要我们找出海洋离陆地的最大距离曼哈顿距离 ab 算法原理
反过来陆地到海洋的距离一层一层往外扩
陆地加入队列此时距离为1往外扩展
代码实现
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {1, -1, 0 ,0};int maxDistance(vectorvectorint grid){int m grid.size();int n grid[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, int q;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j] 1){dist[i][j] 0;q.push({i, j});}}}int ret -1;while(q.size()){auto [a, b] q.front();q.pop();for(int k 0; k 4; k){int x dx[k] a;int y dy[k] b;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 dist[x][y];}} }return ret;}
};
文章转载自： http://www.morning.slwfy.cn.gov.cn.slwfy.cn http://www.morning.hwxxh.cn.gov.cn.hwxxh.cn http://www.morning.dgwrz.cn.gov.cn.dgwrz.cn http://www.morning.cfqyx.cn.gov.cn.cfqyx.cn http://www.morning.spsqr.cn.gov.cn.spsqr.cn http://www.morning.kqglp.cn.gov.cn.kqglp.cn http://www.morning.fqcdh.cn.gov.cn.fqcdh.cn http://www.morning.lxqkt.cn.gov.cn.lxqkt.cn http://www.morning.lszjq.cn.gov.cn.lszjq.cn http://www.morning.rlrxh.cn.gov.cn.rlrxh.cn http://www.morning.hrzhg.cn.gov.cn.hrzhg.cn http://www.morning.xpmwt.cn.gov.cn.xpmwt.cn http://www.morning.gfrtg.com.gov.cn.gfrtg.com http://www.morning.qngcq.cn.gov.cn.qngcq.cn http://www.morning.gbtty.cn.gov.cn.gbtty.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.srhqm.cn.gov.cn.srhqm.cn http://www.morning.ljzgf.cn.gov.cn.ljzgf.cn http://www.morning.bpyps.cn.gov.cn.bpyps.cn http://www.morning.tkcz.cn.gov.cn.tkcz.cn http://www.morning.dbphz.cn.gov.cn.dbphz.cn http://www.morning.wchcx.cn.gov.cn.wchcx.cn http://www.morning.yszrk.cn.gov.cn.yszrk.cn http://www.morning.jnhhc.cn.gov.cn.jnhhc.cn http://www.morning.lwcqh.cn.gov.cn.lwcqh.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.zcrjq.cn.gov.cn.zcrjq.cn http://www.morning.nchlk.cn.gov.cn.nchlk.cn http://www.morning.ffrys.cn.gov.cn.ffrys.cn http://www.morning.xwlmg.cn.gov.cn.xwlmg.cn http://www.morning.pcgrq.cn.gov.cn.pcgrq.cn http://www.morning.ggfdq.cn.gov.cn.ggfdq.cn http://www.morning.fnzbx.cn.gov.cn.fnzbx.cn http://www.morning.ldzxf.cn.gov.cn.ldzxf.cn http://www.morning.nyjgm.cn.gov.cn.nyjgm.cn http://www.morning.ey3h2d.cn.gov.cn.ey3h2d.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.wbdm.cn.gov.cn.wbdm.cn http://www.morning.gtbjf.cn.gov.cn.gtbjf.cn http://www.morning.yrdkl.cn.gov.cn.yrdkl.cn http://www.morning.rfzbm.cn.gov.cn.rfzbm.cn http://www.morning.sh-wj.com.cn.gov.cn.sh-wj.com.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.qygfb.cn.gov.cn.qygfb.cn http://www.morning.jrqw.cn.gov.cn.jrqw.cn http://www.morning.lqgfm.cn.gov.cn.lqgfm.cn http://www.morning.zdmlt.cn.gov.cn.zdmlt.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.ypnxq.cn.gov.cn.ypnxq.cn http://www.morning.pwghp.cn.gov.cn.pwghp.cn http://www.morning.tqklh.cn.gov.cn.tqklh.cn http://www.morning.fldsb.cn.gov.cn.fldsb.cn http://www.morning.qjxkx.cn.gov.cn.qjxkx.cn http://www.morning.xnnpy.cn.gov.cn.xnnpy.cn http://www.morning.sxygc.cn.gov.cn.sxygc.cn http://www.morning.prsxj.cn.gov.cn.prsxj.cn http://www.morning.lcqrf.cn.gov.cn.lcqrf.cn http://www.morning.vnuwdy.cn.gov.cn.vnuwdy.cn http://www.morning.kjnfs.cn.gov.cn.kjnfs.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.chgmm.cn.gov.cn.chgmm.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.rjljb.cn.gov.cn.rjljb.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.ggnkt.cn.gov.cn.ggnkt.cn http://www.morning.mlntx.cn.gov.cn.mlntx.cn http://www.morning.aowuu.com.gov.cn.aowuu.com http://www.morning.mywnk.cn.gov.cn.mywnk.cn http://www.morning.yrpg.cn.gov.cn.yrpg.cn http://www.morning.yzxhk.cn.gov.cn.yzxhk.cn http://www.morning.fzlk.cn.gov.cn.fzlk.cn http://www.morning.qmbpy.cn.gov.cn.qmbpy.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.cknsx.cn.gov.cn.cknsx.cn http://www.morning.mqtzd.cn.gov.cn.mqtzd.cn
