Untitled

import java.util.*;

public class UserMainCode {
    // Function to count the number of possible connected configurations
    public static int Colonies(int rows, int cols) {
        if (rows <= 0 || cols <= 0) return 0;
        int totalCells = rows * cols;
        // Using bitwise representation for each cell's state: 0 for empty, 1 for filled
        // Hence, we will iterate through all possible states from 1 to (2^totalCells - 1)
        int totalCount = 0;
        for (int state = 1; state < (1 << totalCells); state++) {
            if (isConnected(state, rows, cols)) {
                totalCount++;
            }
        }
        return totalCount;
    }
    
    // Helper function to check if a given state represents a connected configuration
    private static boolean isConnected(int state, int rows, int cols) {
        // Convert state to a 2D grid representation
        boolean[][] grid = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = (state & (1 << (i * cols + j))) != 0;
            }
        }
        
        // Find the first filled cell to start a Depth-First Search (DFS)
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j]) {
                    // Perform DFS to mark all connected cells
                    Set<String> visited = new HashSet<>();
                    dfs(grid, i, j, visited);
                    // If the number of visited cells equals the number of filled cells in the state,
                    // it means all filled cells are connected.
                    return visited.size() == Integer.bitCount(state);
                }
            }
        }
        return false;
    }
    
    // Depth-First Search (DFS) to mark connected cells
    private static void dfs(boolean[][] grid, int row, int col, Set<String> visited) {
        if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length
                || !grid[row][col] || visited.contains(row + "," + col)) {
            return;
        }
        visited.add(row + "," + col);
        dfs(grid, row + 1, col, visited); // down
        dfs(grid, row - 1, col, visited); // up
        dfs(grid, row, col + 1, visited); // right
        dfs(grid, row, col - 1, visited); // left
    }
}