蓝桥杯上岸每日N题第八期(全球变暖)!!!
同步收录
蓝桥杯上岸必背!!!(第五期BFS)
冲刺蓝桥杯省一模板大全来啦 ~
蓝桥杯4月8号就要开始了 ~
距离蓝桥杯省赛倒数第2天
还没背熟模板的伙伴们背起来
真题千千万万遍,蓝桥省一自然现!
日更3000里,蓝桥眷顾你
暴力出奇迹,打表过样例
祝大家4月8号蓝桥杯上岸 ~
不清楚蓝桥杯考什么的点点下方
考点秘籍
蓝桥杯竞赛干货
算法竞赛字符串常用操作总结!!!
往期回顾
蓝桥杯上岸每日N题第一期(一)!!!
蓝桥杯上岸每日N题第一期(二)!!!
蓝桥杯上岸每日N题第一期(三)!!!
蓝桥杯上岸每日N题第二期(一)!!!
蓝桥杯上岸每日N题第三期(一)!!!
蓝桥杯上岸每日N题第四期(最少刷题数)!!!
蓝桥杯上岸每日N题第五期(山)!!!
蓝桥杯上岸每日N题第六期(求阶乘)!!!
蓝桥杯上岸必刷专题
蓝桥杯上岸必刷!!!(日期专题+保姆级教学)
蓝桥杯上岸必刷!!!(字符串专题)
蓝桥杯上岸必刷!!!(模拟/枚举专题)
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全(第二期)
蓝桥杯省一你一定不能错过的模板大全(第三期)
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
蓝桥杯上岸必背!!! (第三期 DP)
蓝桥杯上岸必背!!!(第四期DFS)
蓝桥杯上岸必背!!!(第五期BFS)
蓝桥杯上岸必背!!!(第六期树与图的遍历)
蓝桥杯上岸必背!!!(第七期最短路算法)
蓝桥杯上岸每日N题第七期(小猫爬山)!!!
想看JavaB组填空题的伙伴们点点下方
填空题
前言
蓝桥杯后天就要开始啦~还没刷题的同学跟我一起来刷历年真题,迟点出考前鲤鱼锦囊
老爷保佑
喜欢的小伙伴可以关注我,关注寸铁,我们一起上岸4.8蓝桥杯!!!
预告
明天出考前冲刺锦囊
全球变暖
考点:BFS+Queue
分析
其中”上下左右”四个方向上
#
连在一起的一片陆地组成一座岛屿。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋.
),它就会被淹没。
题目模拟(岛屿)
注:图中有3个岛屿,上下连续区域。
题目模拟(海洋淹没)
注:题中有一个岛屿全被淹没
题目解读
观察一下:岛屿中陆地的数量和海洋的数量是统一的。
如果这个陆地上下左右方向只要有一个方向有.
的话,就说明该陆地会被淹没。
也就是只要我们在陆地上下左右方向中找到了一个.
,就说明这个陆地被淹没。
换言之,如果说岛屿中陆地被淹没了,就存在至少一个方向的海洋.
。
我们只需要统计岛屿的个数和海洋的个数即可。
如果海洋个数和岛屿中陆地的个数相等,则说明该岛屿已被淹没。否则未被淹没。
所以,关键在于维护海洋和岛屿中陆地的个数。
这题用BFS来处理
首先没有点与点之间的关系,所以我们不用邻接表来存储边和点的关系。
而是用队列的方式去维护BFS一层一层往外搜,一层一层往外扩。
那在bfs中我们还需要维护其他变量用于解决此题。
首先,我们需要去统计连通块(岛屿)中陆地的个数 res。
这里在队头元素出队的时候,统计一下即可。
设定isbound来标记是边界的.
然后,弹出队头,进行上下左右的坐标移动,统计其上下左右方向是否有.
。
有的话,我们就将该位置的坐标标记上false。
最后统计一下每个岛屿的isbound的个数有多少个。
如果说res和isbound相等,则说明该岛屿全部淹没。
代码
import java.util.*;
public class Main{
static int N=1010;
static char g[][]=new char[N][N];
static boolean st[][]=new boolean [N][N];
static int dx[]= {1,0,-1,0};
static int dy[]= {0,-1,0,1};
static int n;
static int cnt;
public static void main(String []args) {
Scanner in=new Scanner(System.in);
n=in.nextInt();
for(int i=0;i<n;i++) {
char a[]=in.next().toCharArray();
for(int j=0;j<n;j++) {
g[i][j]=a[j];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(g[i][j]=='#'&&!st[i][j]) {
if(bfs(i,j))cnt++;
}
}
}
System.out.println(cnt);
}
public static boolean bfs(int x,int y) {
Queue<pair>q=new LinkedList<>();
q.add(new pair(x,y));
int res=0;
int bound=0;
st[x][y]=true;
while(!q.isEmpty()) {
pair t=q.poll();
res++;
boolean isbound=false;
for(int i=0;i<4;i++) {
int a=t.x+dx[i];
int b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=n)continue;
if(st[a][b])continue;
if(g[a][b]=='.') {
isbound=true;
continue;
}
q.add(new pair(a, b));
st[a][b]=true;
}
if(isbound)bound++;
}
return res==bound;
}
}
class pair{
int x;
int y;
public pair(int x,int y) {
this.x=x;
this.y=y;
}
}