题目描述

抽象题意：
（1）求图的连通块数，（2）求max（每个连通块的面积）

思路

（对于1）
（对于2）每个连通块的面积=入队/出队的点数。

难点

算法1

java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int N=55,M=55;
    public static int n,m;
    public static int[][] g=new int[N][M];
    public static boolean[][] st=new boolean[N][M];
    public static Queue<Pair1> q=new LinkedList<>();
    public static int res,area;
    public static int[] dx={0,-1,0,1};
    public static int[] dy={-1,0,1,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for(int i=0;i<n;i++){
            String[] s1 = br.readLine().split(" ");
            for(int j=0;j<m;j++){
                g[i][j]=Integer.parseInt(s1[j]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!st[i][j]){
                    area=Math.max(area,bfs(i,j));
                    res++;
                }
            }
        }
        System.out.println(res);
        System.out.println(area);
    }
    public static int bfs(int sx,int sy){
        int area=0;
        Pair1 p=new Pair1(sx,sy);
        q.add(p);
        st[sx][sy]=true;
        while(!q.isEmpty()){
            Pair1 t=q.poll();
            area++;
            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>=m){
                    continue;
                }
                if(st[x][y] || (g[t.x][t.y]>>i&1)==1){
                    continue;
                }
                q.add(new Pair1(x,y));
                st[x][y]=true;
            }
        }
        return area;
    }
}
class Pair1{
    int x;
    int y;
    public Pair1(int x,int y){
        this.x=x;
        this.y=y;
    }
}