Untitled

mail@pastecode.io avatar
unknown
java
7 months ago
2.1 kB
6
Indexable
Never
public class UserMainCode {

    // The count variable keeps track of the number of valid arrangements.
    private static int count = 0;
    
    // Method to initialize the process and return the count of arrangements.
    public static int Colonies(int input1, int input2) {
        count = 0; // Reset count for each call.
        boolean[][] visited = new boolean[input1][input2];
        findArrangements(visited, 0, 0, input1 * input2);
        return count;
    }
    
    // Recursive method to find all valid arrangements of colonies.
    private static void findArrangements(boolean[][] visited, int startRow, int startCol, int remaining) {
        // If there are no remaining places to fill, we have a valid arrangement.
        if (remaining == 0) {
            count++;
            return;
        }
        
        for (int row = startRow; row < visited.length; row++) {
            for (int col = (row == startRow ? startCol : 0); col < visited[0].length; col++) {
                // Place a colony if the current cell is not visited and it has an adjacent colony.
                if (!visited[row][col] && hasAdjacentColony(visited, row, col)) {
                    visited[row][col] = true;
                    findArrangements(visited, row, col, remaining - 1);
                    visited[row][col] = false; // Backtrack
                }
            }
        }
    }
    
    // Method to check if the current cell has an adjacent colony.
    private static boolean hasAdjacentColony(boolean[][] visited, int row, int col) {
        int[] rowOffsets = {-1, 1, 0, 0};
        int[] colOffsets = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int newRow = row + rowOffsets[i];
            int newCol = col + colOffsets[i];
            if (newRow >= 0 && newRow < visited.length && newCol >= 0 && newCol < visited[0].length && visited[newRow][newCol]) {
                return true;
            }
        }
        // If this is the first cell, start the colony here.
        return row == 0 && col == 0;
    }
}
Leave a Comment