TzWccS3BalsColor Solution Brute Force DFS

TzWccS3BalsColor.java

import java.util.Arrays;

public class TzWccS3BalsColor {
    public static void main(String[] args) {

        // Visible tests
        char[][] board = new char[][] { 
            { 'B', 'B', 'G', 'O' }, 
            { 'R', 'B', 'B', 'O' }, 
            { 'Y', 'O', 'G', 'Y' } 
        };
        System.out.println(tzWccS3BalsColor(board, 2)); // EO = 4

        board = new char[][] { 
            { 'B', 'B' }, 
            { 'B', 'B' } 
        };
        System.out.println(tzWccS3BalsColor(board, 8)); // EO = 16

        board = new char[][] { 
            { 'G', 'Y', 'B' }, 
            { 'Y', 'R', 'O' }, 
            { 'O', 'Y', 'B' } 
        };
        System.out.println(tzWccS3BalsColor(board, 2)); // EO = 2

        board = new char[][] { 
            { 'O', 'O', 'G', 'Y', 'Y' }, 
            { 'O', 'R', 'O', 'Y', 'Y' }, 
            { 'B', 'Y', 'R', 'G', 'B' },
            { 'G', 'B', 'B', 'Y', 'R' }, 
            { 'B', 'B', 'R', 'R', 'G' } 
        };
        System.out.println(tzWccS3BalsColor(board, 1)); // EO = 4

        // Edge cases
        board = new char[][] { 
            { 'G', 'G', 'G' }, 
            { 'G', 'R', 'G' }, 
            { 'G', 'G', 'G' } 
        };
        System.out.println(tzWccS3BalsColor(board, 1)); // EO = 4

        board = new char[][] { 
            { 'G', 'G', 'G' }, 
            { 'G', 'R', 'G' }, 
            { 'G', 'G', 'G' } 
        };
        System.out.println(tzWccS3BalsColor(board, 2)); // EO = 8

        board = new char[][] { 
            { 'B', 'B', 'G', 'Y' },
            { 'B', 'O', 'O', 'O' },
            { 'Y', 'B', 'O', 'Y' },
            { 'G', 'R', 'R', 'Y' },
        };
        System.out.println(tzWccS3BalsColor(board, 3)); // EO = 13

        board = new char[][] { 
            { 'G', 'G', 'G' }, 
            { 'G', 'R', 'G' }, 
            { 'G', 'G', 'G' } 
        };
        System.out.println(tzWccS3BalsColor(board, 8)); // EO = 32, TLE
    }

    static int boardHeight;
    static int boardWidth;
    static int maxScore;

    private static int tzWccS3BalsColor(char[][] board, int remainingTurns) { // remainingTurns = k

        maxScore = 0;
        boardHeight = board.length;
        boardWidth = board[0].length;

        runDFS(remainingTurns, 0, board);
        return maxScore;
    }

    private static void runDFS(int remainingTurns, int currentPoints, char[][] currentBoardState) {

        if (remainingTurns == 0) {
            maxScore = Math.max(currentPoints, maxScore);
            return;
        }

        for (int rStart = 0; rStart <= boardHeight - 2; rStart++) {
            for (int cStart = 0; cStart <= boardWidth - 2; cStart++) {

                int chunkHeight = boardHeight - rStart;
                int chunkWidth = boardWidth - cStart;

                for (int rSize = 2; rSize <= chunkHeight; rSize++) {
                    for (int cSize = 2; cSize <= chunkWidth; cSize++) {

                        int maxShift = rSize * cSize - 1;

                        for (int s = 0; s < maxShift; s++) {
                            char[][] shiftedBoardState = copy(currentBoardState);

                            for (int c = 0; c < s; c++) {
                                shift(shiftedBoardState, rSize, cSize, rStart, cStart);
                            }

                            int newCalculatedPoints = calcPoints(shiftedBoardState);

                            runDFS(remainingTurns - 1, currentPoints + newCalculatedPoints, shiftedBoardState);
                        }

                    }
                }

            }
        }
    }

    private static void shift(char[][] toCheckBoard, int height, int width, int rStart, int cStart) {
        char temp = toCheckBoard[rStart + 1][cStart];

        for (int i = rStart + 1; i < rStart + height - 1; i++) {
            toCheckBoard[i][cStart] = toCheckBoard[i + 1][cStart];
        }

        for (int i = cStart; i < cStart + width - 1; i++) {
            toCheckBoard[rStart + height - 1][i] = toCheckBoard[rStart + height - 1][i + 1];
        }

        for (int i = rStart + height - 1; i > rStart; i--) {
            toCheckBoard[i][cStart + width - 1] = toCheckBoard[i - 1][cStart + width - 1];
        }

        for (int i = cStart + width - 1; i > cStart; i--) {
            toCheckBoard[rStart][i] = toCheckBoard[rStart][i - 1];
        }

        toCheckBoard[rStart][cStart] = temp;
    }

    private static char[][] copy(char[][] board) {

        char[][] copy = new char[boardHeight][];

        for (int i = 0; i < boardHeight; i++) {
            copy[i] = Arrays.copyOf(board[i], boardWidth);
        }

        return copy;
    }

    private static int calcPoints(char[][] currentBoardState) {
        int[] rbgyoCount = new int[] { 0, 0, 0, 0, 0 };

        int index = 0;
        for (char currentColor : "RBGYO".toCharArray()) {
            int count = countSquares(currentBoardState, currentColor);
            count++;
            rbgyoCount[index] = count;
            index++;
        }

        int total = 1;

        for (int c : rbgyoCount) {
            total *= c;
        }

        return total;
    }

    private static int countSquares(char[][] currentBoardState, char currentColor) {
        int count = 0;
        for (int rstart = 0; rstart <= currentBoardState.length - 2; rstart++) {
            o: for (int cstart = 0; cstart <= currentBoardState[0].length - 2; cstart++) {
                for (int r = 0; r < 2; r++) {
                    for (int c = 0; c < 2; c++) {
                        if (currentBoardState[rstart + r][cstart + c] != currentColor) {
                            continue o;
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }
}