public class Islands {
    // No of rows and columns
    static final int ROW = 4, COL = 5;
    // A function to check if a given cell (row, col) can
    // be included in DFS
    static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
        // row number is in range, column number is in range
        // and value is 1 and not yet visited
        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
    }
    // A utility function to do DFS for a 2D boolean matrix.
    // It only considers the 8 neighbors as adjacent vertices
    static void DFS(int M[][], int row, int col, boolean visited[][]) {
        // These arrays are used to get row and column numbers
        // of 8 neighbors of a given cell
        int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
        int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
        // Mark this cell as visited
        visited[row][col] = true;
        // Recur for all connected neighbours
        for (int k = 0; k < 8; ++k)
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
                DFS(M, row + rowNbr[k], col + colNbr[k], visited);
    }
    // The main function that returns count of islands in a given
    // boolean 2D matrix
    static int countIslands(int M[][]) {
        // Make a bool array to mark visited cells.
        // Initially all cells are unvisited
        boolean visited[][] = new boolean[ROW][COL];
        // Initialize count as 0 and traverse through all the cells
        // of the given matrix
        int count = 0;
        for (int i = 0; i < ROW; ++i)
            for (int j = 0; j < COL; ++j)
                if (M[i][j] == 1 && !visited[i][j]) // If a cell with
                { // value 1 is not
                    // visited yet, then a new island is found. Visit all
                    // cells in this island and increment island count
                    DFS(M, i, j, visited);
                    ++count;
                }
        return count;
    }
    // Driver method
    public static void main(String[] args) throws java.lang.Exception {
        int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
        System.out.println("Number of islands is: " + countIslands(M));
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Islands {
    // 行和列的数量
    static final int ROW = 4, COL = 5;
    static int size;
    // 一个函数，用于检查给定的单元格（行、列）是否可以包含在DFS中
    static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
        // 行号在范围内，列号在范围内
        // 值为1且尚未被访问
        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
    }
    // 用于执行2D布尔矩阵的DFS的实用函数。
    // 它只将8个相邻的单元格视为相邻的顶点
    static void DFS(int M[][], int row, int col, boolean visited[][]) {
        // 这些数组用于获取给定单元格的8个相邻单元格的行号和列号
        int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
        int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
        // 将此单元格标记为已访问
        visited[row][col] = true;
        size++;
        // 递归访问所有相邻的邻居
        for (int k = 0; k < 8; ++k)
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
                DFS(M, row + rowNbr[k], col + colNbr[k], visited);
    }
    
    // 返回给定布尔2D矩阵中各个岛屿的大小的主要函数
    static List<Integer> sizeIslands(int M[][]) {
        // 创建一个布尔数组以标记已访问的单元格。
        // 最初所有单元格都未被访问
        boolean visited[][] = new boolean[ROW][COL];
        // 初始化空列表，并遍历给定矩阵的所有单元格
        List<Integer> listSizes = new ArrayList<Integer>();
        for (int i = 0; i < ROW; ++i)
            for (int j = 0; j < COL; ++j)
                if (M[i][j] == 1 && !visited[i][j]) // 如果值为1的单元格尚未被访问
                {
                    // 则找到新的岛屿，访问此岛屿中的所有单元格并增加岛屿大小
                    size = 0;
                    DFS(M, i, j, visited);
                    listSizes.add(size);
                }
        return listSizes;
    }
    // 主方法
    public static void main(String[] args) throws java.lang.Exception {
        int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
        List<Integer> list = sizeIslands(M);
        Collections.sort(list);
        System.out.println("Sizes of islands are: " + list);
    }
}