Untitled

mail@pastecode.io avatar
unknown
java
7 months ago
2.0 kB
5
Indexable
Never
public class UserMainCode {
    // Function to check if a colony is valid by ensuring all cells are connected
    private static boolean isValidColony(boolean[][] colony, int m, int n) {
        // Find the first cell of the colony to start the search
        int startRow = -1, startCol = -1;
        for (int i = 0; i < m && startRow == -1; i++) {
            for (int j = 0; j < n && startCol == -1; j++) {
                if (colony[i][j]) {
                    startRow = i;
                    startCol = j;
                }
            }
        }
        
        // If no cell is part of the colony, it's valid by default
        if (startRow == -1) return true;
        
        // Perform a depth-first search to check connectivity
        boolean[][] visited = new boolean[m][n];
        dfs(colony, visited, startRow, startCol);
        
        // If any cell in the colony is not visited, the colony is not valid
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (colony[i][j] && !visited[i][j]) return false;
            }
        }
        
        return true;
    }
    
    // Depth-first search to mark all reachable cells in the colony
    private static void dfs(boolean[][] colony, boolean[][] visited, int row, int col) {
        if (row < 0 || row >= colony.length || col < 0 || col >= colony[0].length || visited[row][col] || !colony[row][col]) {
            return;
        }
        
        visited[row][col] = true;
        dfs(colony, visited, row + 1, col); // Down
        dfs(colony, visited, row - 1, col); // Up
        dfs(colony, visited, row, col + 1); // Right
        dfs(colony, visited, row, col - 1); // Left
    }
    
    // Function to count the number of valid colonies
    public static int Colonies(int input1, int input2) {
        int m = input1, n = input2;
        int count = 0;
        
        // Go through all possible subsets of cells
        for (int mask = 0; mask <
Leave a Comment