DAY52-图论BFS

2024-08-26 03:44
文章标签 图论 bfs day52

本文主要是介绍DAY52-图论BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

kama101.孤岛的总面积 

	/*** 在外循环遇到没有标记过的岛屿+1* @param args*/public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n][m];boolean[][] path = new boolean[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {isoland[i][j]=scan.nextInt();}}//初始化_把连着四周的陆地变为海洋for(int i=0;i<m;i++) {if(isoland[0][i]==1&&path[0][i]==false) {bfs0(isoland,path,0,i,n,m);}if(isoland[n-1][i]==1&&path[n-1][i]==false) {bfs0(isoland,path,n-1,i,n,m);}}for(int i=1;i<n-1;i++) {if(isoland[i][0]==1&&path[i][0]==false) {bfs0(isoland,path,i,0,n,m);}if(isoland[i][m-1]==1&&path[i][m-1]==false) {bfs0(isoland,path,i,m-1,n,m);}}for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {System.out.print(isoland[i][j]);}System.out.println();}//DFS搜索for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(isoland[i][j]==1&&path[i][j]==false) {bfs(isoland,path,i,j,n,m);}}}System.out.println(sum);scan.close();}public static int sum=0;public static int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};/*** 初始化为0* @param isoland* @param path* @param x* @param y*/public static void bfs0(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;isoland[x][y]=0;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;isoland[tempx][tempy]=0;queue.add(new int[] {tempx,tempy});}}}}/*** 从哪个点开始广度搜索* @param isoland* @param path* @param x* @param y*/public static void bfs(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;sum++;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;sum++;queue.add(new int[] {tempx,tempy});}}}}

kama102.沉没孤岛 

	/*** 在外循环遇到没有标记过的岛屿+1* @param args*/public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n][m];boolean[][] path = new boolean[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {isoland[i][j]=scan.nextInt();}}//初始化_把连着四周的陆地变为海洋for(int i=0;i<m;i++) {if(isoland[0][i]==1&&path[0][i]==false) {bfs(isoland,path,0,i,n,m);}if(isoland[n-1][i]==1&&path[n-1][i]==false) {bfs(isoland,path,n-1,i,n,m);}}for(int i=1;i<n-1;i++) {if(isoland[i][0]==1&&path[i][0]==false) {bfs(isoland,path,i,0,n,m);}if(isoland[i][m-1]==1&&path[i][m-1]==false) {bfs(isoland,path,i,m-1,n,m);}}//DFS搜索for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(isoland[i][j]==1&&path[i][j]==false) {bfs0(isoland,path,i,j,n,m);}}}for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {System.out.print(isoland[i][j]);if(j!=m-1) {System.out.print(" ");}}if(i!=n-1) {System.out.println();			}}scan.close();}public static int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};/*** 初始化为0* @param isoland* @param path* @param x* @param y*/public static void bfs0(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;isoland[x][y]=0;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;isoland[tempx][tempy]=0;queue.add(new int[] {tempx,tempy});}}}}/*** 从哪个点开始广度搜索* @param isoland* @param path* @param x* @param y*/public static void bfs(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;queue.add(new int[] {tempx,tempy});}}}}

kama103.水流问题 

	/***从四周遍历获取两边都可以到达的地方* @param args*/public static void main(String[] args) {//获取岛屿数组Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n][m];boolean[][] pathL = new boolean[n][m];boolean[][] pathR = new boolean[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {isoland[i][j]=scan.nextInt();}}//遍历上边界和下边界for(int i=0;i<m;i++) {if(pathL[0][i]==false) {bfs(isoland,pathL,0,i,n,m);}if(pathR[n-1][i]==false) {bfs(isoland,pathR,n-1,i,n,m);}}//遍历左边界和右边界for(int i=0;i<n;i++) {if(pathL[i][0]==false) {bfs(isoland,pathL,i,0,n,m);}if(pathR[i][m-1]==false) {bfs(isoland,pathR,i,m-1,n,m);}}for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(pathL[i][j]==true&&pathR[i][j]==true) {System.out.println(i+" "+j);}}}scan.close();}public static int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};/*** 从哪个点开始广度搜索* @param isoland* @param path* @param x* @param y*/public static void bfs(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]>=isoland[temp[0]][temp[1]]&&path[tempx][tempy]==false) {path[tempx][tempy]=true;queue.add(new int[] {tempx,tempy});}}}}

kama104.建造最大岛屿

	/*** 遍历每个岛并编号、再遍历所有的0将0周围的所有值加起来* @param args*/public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n][m];boolean[][] path = new boolean[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {isoland[i][j]=scan.nextInt();}}//BFS遍历for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(isoland[i][j]==1&&path[i][j]==false) {bfs0(isoland,path,i,j,n,m);hash.put(count, area);count++;area=0;}}}//会出现重复计算一个岛屿的问题int max=0;for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {//如果该位置是海洋if(isoland[i][j]==0) {int sub=0;set.clear();for(int k=0;k<4;k++) {int tempx=i+step[k][0];int tempy=j+step[k][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==0) continue;if(set.contains(isoland[tempx][tempy]))continue;sub=sub+hash.get(isoland[tempx][tempy]);set.add(isoland[tempx][tempy]);}sub++;if(sub>max)max=sub;}}}scan.close();//说明没有海洋部分,返回整个陆地部分if(max==0) {System.out.println(hash.get(2));return ;}System.out.println(max);}public static int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};//编号与mappublic static Map<Integer,Integer> hash = new HashMap<>();public static Set<Integer> set = new HashSet<>();public static int count=2;public static int area=0;/*** 初始化为0* @param isoland* @param path* @param x* @param y*/public static void bfs0(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;isoland[x][y]=count;area++;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;isoland[tempx][tempy]=count;area++;queue.add(new int[] {tempx,tempy});}}}}/*** 从哪个点开始广度搜索* @param isoland* @param path* @param x* @param y*/public static void bfs(int[][] isoland,boolean[][] path,int x,int y,int n,int m) {LinkedList<int[]> queue = new LinkedList<>();queue.add(new int[]{x,y});path[x][y]=true;while(!queue.isEmpty()) {int[] temp = queue.remove();for(int i=0;i<4;i++) {int tempx=temp[0]+step[i][0];int tempy=temp[1]+step[i][1];//越界if(tempx<0||tempx>n-1||tempy<0||tempy>m-1) continue;if(isoland[tempx][tempy]==1&&path[tempx][tempy]==false) {path[tempx][tempy]=true;queue.add(new int[] {tempx,tempy});}}}}

这篇关于DAY52-图论BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1107458。

相关文章

hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为
阅读更多...
POJ 3057 最大二分匹配+bfs + 二分

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...
【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一：卡码网 103. 水流问题 题目链接 题解：DFS 题目二：卡码网 104. 建造最大岛屿 题目链接 题解：DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节，还是选择使用 DFS 来解决这类搜索问题（单纯因为我更熟悉 DFS 一点），今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚
阅读更多...
双头BFS

双头BFS

牛客月赛100 D题，过了80%数据，调了一下午。。。烦死了。。。 还是没调试出来，别人的代码用5维的距离的更新有滞后性，要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
【CF】D. Arthur and Walls（BFS + 贪心）

【CF】D. Arthur and Walls（BFS + 贪心）

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’，如果有的话这个*就需要变成‘.’，利用BFS进行遍历，入队的要求是这个点为. 一开始将所有的'.'全部加入队列，如果碰到一个'*'变成'.'就入队，判断的时候从4个方向就行判断 题目链接：http://codeforces.com/contest/525/problem/D #include<cstdio>#include<
阅读更多...
hdu2717(裸bfs广搜)

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接： http://acm.hdu.edu.cn/showproblem.
阅读更多...
Codeforces#295(Div.2)A、B(模拟+BFS)

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接：点击打开链接 C. 题目链接：点击打开链接 解题思路： 对于给定的字符串，取出现次数最多的字母（可以同时有多个）。由这些字母组成长度为n的字符串，求有多少种组合。最后用数学知识即可。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <climits>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2