In this HackerRank Brick Tiling problem solution, we have given a grid having N rows and M columns. A grid square can either be blocked or empty. Blocked squares are represented by a '#' and empty squares are represented by '.'. Find the number of ways to tile the grid using L-shaped bricks. An L brick has one side of length three units while the other of length 2 units. All empty squares in the grid should be covered by exactly one of the L-shaped tiles, and blocked squares should not be covered by any tile. The bricks can be used in any orientation (they can be rotated or flipped).

## Problem solution in Python.

```def memoize(func):
pool = {}
def wrapper(*arg):
if arg not in pool:
pool[arg] = func(*arg)
return pool[arg]
return wrapper

mod = 1000000007
shapes = (\
((1,0),(2,0),(2,1)),\
((0,1),(0,2),(-1,2)),\
((0,1),(1,1),(2,1)),\
((1,0),(0,1),(0,2)),\
((0,1),(-1,1),(-2,1)),\
((0,1),(0,2),(1,2)),\
((1,0),(2,0),(0,1)),\
((1,0),(1,1),(1,2)))

for case in range(int(input())):
Y,X = map(int,input().split())
mx = [int(''.join('0' if c =='.' else '1' for c in input().rstrip()), 2) for i in range(Y)]
mx = mx + 3*[0]
full = (1<<X)-1

@memoize
def rec(y,first,second,third):
if y==Y:
return 1 if first == second and second == third and third == 0 else 0
if first == full:
return rec(y+1,second,third,mx[y+3])

def can_fit(rows,shape,x_offset):
res = rows[:]
for x,y in shape:
x += x_offset
if x < 0 or x >= X or y < 0 or y >= Y:
return None
if res[y] & (1<<x) != 0:
return None
res[y] |= (1<<x)
return res

free = 0
while (first & (1<<free)) != 0:
free += 1
rows = [first | (1<<free),second,third]
ans = 0
for shape in shapes:
nrows = can_fit(rows,shape,free)
if nrows != None:
ans = (ans + rec(y, *nrows)) % mod
return ans

print(rec(0,mx[0],mx[1],mx[2]))
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {

static int MOD = 1000000007;

static int[][][] patterns = {
{{0, 0}, {0, 1}, {1, 0}, {2, 0}},
{{0, 0}, {0, 1}, {0, 2}, {1, 2}},
{{0, 0}, {1, 0}, {2, 0}, {2, -1}},
{{0, 0}, {1, 0}, {1, 1}, {1, 2}},
{{0, 0}, {0, 1}, {1, 1}, {2, 1}},
{{0, 0}, {1, 0}, {1, -1}, {1, -2}},
{{0, 0}, {1, 0}, {2, 0}, {2, 1}},
{{0, 0}, {1, 0}, {0, 1}, {0, 2}},
};

static boolean canApply(int[][] pattern, int[] arr, int x, int y, int rows, int cols) {
for (int[] p : pattern) {
int nx = x + p[0];
int ny = y + p[1];
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || (arr[nx] & (1 << (cols - ny - 1))) > 0) {
return false;
}
}
return true;
}

static void setValue(int[][] pattern, int[] arr, int x, int y, int rows, int cols, int val) {
for (int[] p : pattern) {
int nx = x + p[0];
int ny = y + p[1];
if (val == 1) {
arr[nx] = arr[nx] | (1 << (cols - ny - 1));
} else {
arr[nx] = arr[nx] & ~(1 << (cols - ny - 1));
}
}
}

static void printArr(int[] arr, int rows, int cols) {
for (int i = 0; i < rows; i++) {
StringBuilder s = new StringBuilder();
for (int j = 0; j < cols; j++) {
s.append((arr[i] & (1 << (cols - j - 1))) > 0 ? '#' : '.');
}
System.out.println(s);
}
System.out.println();
}

static int[] copy(int[] arr) {
int[] narr = new int[arr.length];
System.arraycopy(arr, 0, narr, 0, arr.length);
return narr;
}

static int calc(int[] arr, int rows, int cols, Map<Integer, Integer> memo, Map<Integer, int[]> memo2) {
int hash = Arrays.hashCode(arr);
if (memo.containsKey(hash) && Arrays.equals(arr, memo2.get(hash))) {
return memo.get(hash);
}

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int matched = arr[i] & 1 << (cols - j - 1);
if (matched == 0) {
int ans = 0;
for (int[][] pattern : patterns) {
if (canApply(pattern, arr, i, j, rows, cols)) {
setValue(pattern, arr, i, j, rows, cols, 1);
ans += calc(arr, rows, cols, memo, memo2);
ans %= MOD;
setValue(pattern, arr, i, j, rows, cols, 0);
}
}
memo.put(hash, ans);
memo2.put(hash, copy(arr));
return ans;
}
}
}

memo.put(hash, 1);
memo2.put(hash, copy(arr));
return 1;
}

/*
* Complete the brickTiling function below.
*/
static int brickTiling(String[] grid) {
/*
*/
int rows = grid.length;
int cols = grid[0].length();

int[] arr = new int[rows];
for (int i = 0; i < rows; i++) {
int val = 0;
for (int k = 0; k < cols; k++) {
if (grid[i].charAt(k) == '#') {
val |= (1 << (cols - k - 1));
}
}
arr[i] = val;
}

return calc(arr, rows, cols, new HashMap<>(), new HashMap<>());
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int tItr = 0; tItr < t; tItr++) {
String[] nm = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

String[] grid = new String[n];

for (int gridItr = 0; gridItr < n; gridItr++) {
String gridItem = scanner.nextLine();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
grid[gridItr] = gridItem;
}

int result = brickTiling(grid);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

ll ways[25][260][260];
ll mod = 1000000007;
vector<pair<int, int> > upWays[260][10];
bool computed[260][10];
int n, m;

int map[25];

vector<pair<int, int> >& getUpWays(int fill, int w){
if(computed[fill][w]) return upWays[fill][w];
// printf("up ways%d\n", fill);
computed[fill][w] = true;
if(fill == 0){
upWays[fill][w].push_back(make_pair(0, 0));
return upWays[fill][w];
}
vector<pair<int, int> >& ways = upWays[fill][w];
for(int i = 0; i < w; i++){
if(fill & (1<<i)){
int up = 1<<i, upup = 3<<i;
vector<pair<int, int> >& prev = getUpWays(fill - (1<<i), w);
if(i + 1 < w){
for(auto p : prev){
if(p.first & upup) continue;
if(p.second & up) continue;
ways.push_back(make_pair(p.first | upup, p.second | up));
}
}
if(i > 0){
upup = 3<<(i - 1);
for(auto p : prev){
if(p.first & upup) continue;
if(p.second & up) continue;
ways.push_back(make_pair(p.first | upup, p.second | up));
}
}
if(i + 2 < w){
for(auto p : prev){
if(p.second & 7<<i)continue;
ways.push_back(make_pair(p.first, p.second | (7<<i)));
}
}
if(i > 1){
up = 7<<(i - 2);
for(auto p : prev){
if(p.second & up)continue;
ways.push_back(make_pair(p.first, p.second | up));
}
}
if(i == w - 1 || (3<<i) - (fill & (3<<i)))  break;
up = 1<<i;
vector<pair<int, int> >& pprev = getUpWays(fill - (3<<i), w);
for(auto p : pprev){
if(!(p.first & (1<<i)) && !(p.second & (1<<i))){
ways.push_back(make_pair(p.first | (1<<i), p.second | (1<<i)));
}
if(!(p.first & (2<<i)) && !(p.second & (2<<i))){
ways.push_back(make_pair(p.first | (2<<i), p.second | (2<<i)));
}
}
if(i == w - 2 || (7<<i) - (fill & (7<<i))) break;
vector<pair<int, int> >& ppprev = getUpWays(fill - (7<<i), w);
for(auto p : ppprev) {
if(!(p.second & (1<<i))){
ways.push_back(make_pair(p.first, p.second | (1<<i)));
}
if(!(p.second & (4<<i))){
ways.push_back(make_pair(p.first, p.second | (4<<i)));
}
}
break;
}
}
return ways;
}

ll getWays(int row, int row1, int row2){
// printf("call %d %d %d\n", row, row1, row2);
if(row < -2){
return 0;
}
if(row == -2){
return (row1 == (1<<m) - 1) && (row2 == (1<<m) - 1) ? 1 : 0;
}
if(row == -1){
// printf("%d %d %d\n", row, row1, row2);
return (row1 == (1<<m) - 1) && (row2 == map[0]) ? 1 : 0;
}
if(ways[row][row1][row2] != -1) return ways[row][row1][row2];
if(map[row] - (row1 & map[row]) ||
map[row + 1] - (row2 & map[row + 1])) return ways[row][row1][row2] = 0;

int fill1 = row1 - map[row],
fill2 = row2 - map[row + 1];

if(fill1 == 0 && fill2 == 0) return ways[row][row1][row2] = getWays(row - 2, (1<<m) - 1, (1<<m) - 1);
if(fill2 == 0) return ways[row][row1][row2] = getWays(row - 1, (1<<m) - 1, fill1 + map[row]);
if(fill1 == 0) return ways[row][row1][row2] = 0;

ll r = 0;
// printf("%d %d %d\n", row, fill1, fill2);
vector<pair<int, int> >& upWay = getUpWays(fill2, m);
for(auto u : upWay){
int r1 = u.first, r2 = u.second;
// printf("fill %d %d\n", r1, r2);
if(r2 - (fill1 & r2)) continue;
r += getWays(row - 1, (1<<m) - 1 - r1, fill1 - r2 + map[row]);
r %= mod;
}

return ways[row][row1][row2] = r;
}

int main(){
int t;
scanf("%d", &t);
char row[20];
for(int i = 0; i < 260; i++)for(int j = 0; j < 10; j++){
computed[i][j] = false;
}
while(t--){
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%s", row);
int mm = 0;
for(int j = 0; j < m; j++){
if(row[j] == '#'){
mm |= 1<<j;
}
}
map[i] = mm;
}
for(int i = 0; i < n; i++)for(int j = 0; j < (1<<m); j++)for(int k = 0; k < (1<<m); k++){
ways[i][j][k] = -1;
}
printf("%lld\n", getWays(n - 2, (1<<m) - 1, (1<<m) - 1));
}
return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include "assert.h"
#include "stdio.h"

#define rep(i,n) for(i=0;i<(n);i++)

#define MOD 1000000007
#define N 25
#define M 8
#define B 8

int n, m, tm, tm2, grid[N], ways[N][1<<(2*M)], width[B] = { 1, 1, 1, 1, 2, 2, 3, 3 }, b[M][B];
char buf[M+1];

int make_brick( int a, int b, int c, int d )
{
return ( tm2 * a + tm * b + c ) << d;
}

void rec( int x, int y, int s0, int s1 )
{
if( y == m )
{
ways[x+1][s1] = ( ways[x+1][s1] + ways[x][s0] ) % MOD;
return;
}

if( ( ( s0 / tm ) >> y ) & 1 )
{
rec( x, y + 1, s0, s1 );
return;
}

int i;
rep(i,B) if( b[y][i] && ( ( b[y][i] / tm ) & s0 ) == 0 && ( b[y][i] & s1 ) == 0 )
rec( x, y + width[i], s0, s1 ^ ( b[y][i] % tm2 ) );
}

void run()
{
int i, j;
scanf( "%d%d", &n, &m );
assert( 1 <= n && n <= 20 && 1 <= m && m <= 8 );
tm = 1<<m, tm2 = 1<<(2*m);

rep(i,m)
{
b[i][0] = i + 2 <= m ? make_brick( 1, 1, 3, i ) : 0;
b[i][1] = i - 1 >= 0 ? make_brick( 2, 2, 3, i - 1 ) : 0;
b[i][2] = i + 3 <= m ? make_brick( 1, 7, 0, i ) : 0;
b[i][3] = i - 2 >= 0 ? make_brick( 4, 7, 0, i - 2 ) : 0;
b[i][4] = i + 2 <= m ? make_brick( 3, 1, 1, i ) : 0;
b[i][5] = i + 2 <= m ? make_brick( 3, 2, 2, i ) : 0;
b[i][6] = i + 3 <= m ? make_brick( 7, 1, 0, i ) : 0;
b[i][7] = i + 3 <= m ? make_brick( 7, 4, 0, i ) : 0;
}

rep(i,n)
{
grid[i] = 0;
scanf( "%s", buf );
rep(j,m) assert( buf[j] == '#' || buf[j] == '.' );
rep(j,m) if( buf[j] == '#' ) grid[i] ^= 1<<j;
}
grid[n] = grid[n+1] = tm-1;

rep(i,n+1) rep(j,tm2) ways[i][j] = 0;
ways[0][ tm * grid[0] + grid[1] ] = 1;
rep(i,n) rep(j,tm2) if( ways[i][j] ) rec( i, 0, j, ( j % tm ) * tm + grid[i+2] );

printf( "%d\n", ways[n][tm2-1] );
}

int main()
{
int t;
scanf( "%d", &t );
assert( 1 <= t && t <= 50 );
while( t-- ) run();
return 0;
}```

{"mode":"full","isActive":false}