class Islands {
    static final int ROW = 5, COL = 5;

    boolean isSafe(int M[][], int row, int col, boolean 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
    int DFS(int M[][], int row, int col, boolean visited[][])
    {
        int rowNbr[] = new int[] { -1, 0, 0, 1 };
        int colNbr[] = new int[] { 0, -1, 1, 0 };

        // Mark this cell as visited
        visited[row][col] = true;

        // Recur for all connected neighbours
        int count = 1;
        for (int k = 0; k < 8; ++k)
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
                count += DFS(M, row + rowNbr[k], col + colNbr[k], visited);

        return count
    }

    boolean diagCheck(int M[][], int row, int col) {
        int rowNbr[] = new int[] { -1, 1, -1,  1 };
        int colNbr[] = new int[] { 1, -1, -1, 1 };

        boolean ans = true;
        for(int k = 0; k < 4; k++) {
            if i >= 0 and i < ROW and j >= 0 and j < COL {
                ans = ans and M[i + rowNbr[k]][j + colNbr[k]] == 0;
            }
        }
        return ans;
    }

    // The main function that returns count of islands in a given
    // boolean 2D matrix
    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 the all cells
        // of given matrix
        int count = 0, temp;
        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 new island found, Visit all
                    // cells in this island and increment island count

                    temp = DFS(M, i, j, visited);
                    if (temp > 1) {
                        ++ count;
                    }
                    else {
                        if diagCheck(M, i, j)
                            count += 1
                    }
                }

        return count;
    }

    // Driver method
    public static void main(String[] args) throws java.lang.Exception
    {
        int M[][] = new int[][] { { 1, 1, 0, 0, 0 },
                                  { 0, 1, 0, 0, 1 },
                                  { 1, 0, 0, 1, 1 },
                                  { 0, 0, 0, 0, 0 },
                                  { 1, 0, 1, 0, 1 } };
        Islands I = new Islands();
        System.out.println("Number of islands is: " + I.countIslands(M));
    }
} // Contributed by Aakash Hasija