题目描述
这个题目真的是完全给跪了,因为发现自己实在是看不懂hhhhh
后来终于在讲解下清晰简单的明白了含义,感觉连通块的问题不会很直白的问你,题目该表达的含义就很简单,需要自己晦涩的看懂样例,并且理解其中的含义。
第二个需要注意的地方就是BFS中,if判断语句,判断当前的格子的四周是不是有墙,如果有墙那么就不可以在该方向上形成连通块
而不是对每一次找到其周围与之相连的4个格子判断是否有墙,这样是毫无作用的
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class point{
int x;
int y;
public point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
public class Main {
public static int N=60,n,m,res=0,ans=0;
public static int g[][]=new int [N][N];
public static boolean st[][]=new boolean [N][N];
public static int dx[]={0,-1,0,1};
public static int dy[]={-1,0,1,0};
public static int bfs(int x,int y) {
int num=0;
Queue<point> queue = new LinkedList<point>();
queue.add(new point(x, y));
st[x][y]=true;
while(!queue.isEmpty())
{
point point=queue.poll();
num++;
for(int i=0;i<4;i++){
int a=point.x+dx[i];
int b=point.y+dy[i];
if(a>=n || a<0 || b>=m || b<0) continue ;
if(st[a][b]) continue;
//此时没有越界也没有被遍历过
//判断当前的这个点的四个方向上有没有墙,如果有墙那么不可以形成连通块
if((g[point.x][point.y]>>i&1)==1) continue;
queue.add(new point(a, b));
st[a][b]=true;
}
}
return num;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader =new BufferedReader(new InputStreamReader(System.in));
String p[]=bufferedReader.readLine().split(" ");
n=Integer.parseInt(p[0]);
m=Integer.parseInt(p[1]);
for(int i=0;i<n;i++){
p=bufferedReader.readLine().split(" ");
for(int j=0;j<m;j++){
g[i][j]=Integer.parseInt(p[j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!st[i][j]){
ans=Math.max(ans,bfs(i,j)) ;
res++;
}
}
}
System.out.println(res);
System.out.println(ans);
}
}
tql
tql