AcWing 1233. 全球变暖
原题链接
简单
作者:
季之秋
,
2021-03-16 22:44:54
,
所有人可见
,
阅读 296
import java.util.*;
public class Main{
static int N=1010,n;
static char g[][]=new char[1010][1010];
static boolean st[][]=new boolean[N][N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int i=0;i<n;i++) {
String s=sc.next();
for(int j=0;j<n;j++){
g[i][j]=s.charAt(j);
}
}
int res=0;
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)) res++; //能不能淹没
}
}
}
System.out.println(res);
}
static int dx[]={0,1,0,-1};
static int dy[]={1,0,-1,0};
static boolean bfs(int a,int b){
st[a][b]=true;
Queue<Node> q=new LinkedList<>();
q.add(new Node(a,b));
int bound=0; //淹没的数量
int total=1; //连通块的所有点 1是起始点
while(!q.isEmpty()){
Node t=q.poll();
boolean t_flag=false; //是否淹没
for(int i=0;i<4;i++){
int x=t.x+dx[i];
int y=t.y+dy[i];
if(x<0||x>=n||y<0||y>=n) continue;
if(st[x][y]) continue; //走到过就不需要再走一遍 不然会一直走到终点爆空间,bfs的精髓
st[x][y]=true; //没走过现在就走到了这个点
if(g[x][y]=='.'){
t_flag=true; //该岛临近海,会被淹没
st[x][y]=false; //大海不能走到,因为一个海可能临近两个不同的岛
//st是为了判重找连通块,这个连通块指的是岛,而不是其他地方
continue;
}
q.add(new Node(x,y)); //剩下的就是陆地,bfs下去
total++; //没走到过 没出界 是个岛 所以新的岛加一
}
if(t_flag) bound++; //可能四周都是海,所以循环后判断 ,被淹没数加一
}
return total==bound;
}
static class Node{
int x,y;
Node(int a,int b){
x=a; y=b;
}
}
}