Java Solution using memoization. The first step is to find all possible Ls that cover the grid, and create a map from grid locations to all valid Ls that cover that location (for the sake of brevity I won’t go over this part, but there’s 8 possible Ls where the ‘long bar’ starts for a single location). The most efficient way to represent the coverage of a grid this small is a bit mask (aka. an array of 3 or less longs), so it also good to idea to precompute the masks for the valid Ls and store them in a map, and also find the mask of the initial grid and fully covered grid. The last map goes from a bitmask to the number of ways you can cover that mask.

The recursive logic is pretty straightforward. Find the first open location on the current grid, and for every L you can place on this location, sum the ways you can cover the rest of the uncovered grid and that’s the number of ways you can cover the current grid. Again, this is all done with bit masks, so you’ll have to implement functions for combining masks, removing coverage from a mask, finding the first open entry and finding the coverage count of a grid (these are all very fast functions though) and a class for a bitmask. Also note that, if you combine a grid’s mask with an L’s mask, and the coverage count went up by less than 4, that means this L overlapped with some already covered part of the grid, and therefore is an invalid placement. You also have to be careful with the last long of the bit mask, as the grid is likely not a multiple of 64 (aka. not all 64 bits of the last long are in use).

Here is the main recursive function (the first call has the “to find” mask as the fully covered grid and the “currently covered” grid as the initially covered grid: ‘ public static long findWaysToCover(BitMask toFindMask, BitMask coveredMask, Map> waysToCover, Map> LsThatCover, Map lToMask, int numLeftToCover, int initialCount) {

    // Avoid recalculations / memoization 
    Map<BitMask,Long> waysToCoverCurr = waysToCover.get(numLeftToCover);
    if (waysToCoverCurr.containsKey(toFindMask)) {
        return waysToCoverCurr.get(toFindMask);
    }
    // Find the first open entry
    int newPosToCover = findFirstOpenEntry(coveredMask);
    Set<Integer> coveringNew = new HashSet<>(LsThatCover.get(newPosToCover));

    // Check every possible way to add an L that covers this open grid location
    long result = 0;
    int currCovered = numToCover - numLeftToCover;
    for (int lIdx : coveringNew) {
        BitMask lMask = lToMask.get(lIdx);
        BitMask nextCovered = combineMasks(coveredMask, lMask);
        // If this L overlaps with the previous coverage, invalid L
        if (findCoverageCount(nextCovered, initialCount) < currCovered + 4) {
            continue;
        }
        // Add this L to the current coverage, find ways to cover the reverse
        BitMask nextToFind = removeCoverage(toFindMask, lMask);
        int newLeftToCover = numLeftToCover - 4;

        long nextWays = findWaysToCover(nextToFind, nextCovered,
        waysToCover, LsThatCover, lToMask, newLeftToCover, initialCount);
        result = (result + nextWays) % mod;
    }
    waysToCoverCurr.put(toFindMask,result);
    return result;
}

‘

from collections import defaultdict import os

MAX_ROWS = 20 MAX_COLS = 8

def set_bit(num, count): return num | (1 << count)

def get_bit(num, i): return (num & (1 << i)) != 0

def clear_bit(num, i): mask = ~(1 << i) return num & mask

class Tile2: def init(self, row1, col1, row2, col2, row3, col3, row4, col4): self.rows = [row1, row2, row3, row4] self.cols = [col1, col2, col3, col4]

def can_fit(self, arr, row, column):
    for i in range(4):
        if row + self.rows[i] < 0 or row + self.rows[i] >= MAX_ROWS or column + self.cols[i] < 0 or column + self.cols[i] >= MAX_COLS:
            return False
        if get_bit(arr[row + self.rows[i]], column + self.cols[i]):
            return False

    for i in range(4):
        arr[row + self.rows[i]] = set_bit(arr[row + self.rows[i]], column + self.cols[i])

    return True

def remove_tile(self, arr, row, column):
    for i in range(4):
        arr[row + self.rows[i]] = clear_bit(arr[row + self.rows[i]], column + self.cols[i])

TILES = [ Tile2(0, 0, 1, 0, 2, 0, 2, 1), Tile2(0, 0, 1, 0, 1, -1, 1, -2), Tile2(0, 0, 0, 1, 1, 1, 2, 1), Tile2(0, 0, 1, 0, 0, 1, 0, 2), Tile2(0, 0, 1, 0, 2, 0, 2, -1), Tile2(0, 0, 0, 1, 0, 2, 1, 2), Tile2(0, 0, 0, 1, 1, 0, 2, 0), Tile2(0, 0, 1, 0, 1, 1, 1, 2) ]

def get_hash(arr): return ''.join(format(num, '02x') for num in arr)

cache = defaultdict(int)

def get_my_count(arr, empty_count): if empty_count % 4 != 0: return 0

count = 0
empty = False

for i in range(MAX_ROWS):
    for j in range(MAX_COLS):
        if not get_bit(arr[i], j):
            empty = True
            for tile in TILES:
                if tile.can_fit(arr, i, j):
                    arr_hash = get_hash(arr)
                    if arr_hash in cache:
                        combinations = cache[arr_hash]
                    else:
                        combinations = get_my_count(arr, empty_count)
                        cache[arr_hash] = combinations
                    count += combinations
                    tile.remove_tile(arr, i, j)
            return count

if count == 0 and not empty:
    return 1

return count

def brickTiling(grid): arr = [0] * MAX_ROWS empty_count = 0 N = len(grid) M = len(grid[0])

for n in range(N):
    for m in range(M):
        if grid[n][m] == '#':
            arr[n] = set_bit(arr[n], m)
        else:
            empty_count += 1

    for m in range(M, MAX_COLS):
        arr[n] = set_bit(arr[n], m)

for n in range(N, MAX_ROWS):
    arr[n] = 255

return get_my_count(arr, empty_count) % 1000000007

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])
    m = int(first_multiple_input[1])

    grid = []

    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)

    result = brickTiling(grid)

    fptr.write(str(result) + '\n')

fptr.close()

Here is my solution in java, javascript,python, C,C++, Chsarp HackerRank Brick Tiling Problem Solution

Here is the solution of Brick Tiling Click here

Here is Brick Tiling problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-brick-tiling-problem-solution.html