Brick Tiling
Problem Statement :
You are 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. A L brick has one side of length three units while 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). Input Format The first line contains the number of test cases T. T test cases follow. Each test case contains N and M on the first line, followed by N lines describing each row of the grid. Constraints 1 <= T <= 50 1 <= N <= 20 1 <= M <= 8 Each grid square will be either '.' or '#'. Output Format Output the number of ways to tile the grid. Output each answer modulo 1000000007.
Solution :
Solution in C :
In C++ :
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <complex>
using namespace std;
// begin insert defines
void Bit(int x, int len = 4, int b = 2) {
vector<int> v;
while (x) {
v.push_back(x % b);
x /= b;
}
while ((int)v.size() < len) v.push_back(0);
for (size_t i = 0; i < v.size(); i++)
cout << v[i];
cout << endl;
}
#define two(x) (1<<(x))
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)
// end insert defines
const int MOD = 1000000007, N = 20, M = 8, B = 1 << M;
int n, m;
int b[N + 2];
int f[2][B][B], cur;
inline void madd(int &a, int b)
{
a += b;
if (a >= MOD) a -= MOD;
}
void dfs(int s0, int s1, int s2, int y, int v)
{
if (y >= m) {
madd(f[cur][s1][s2], v);
// Bit(s0), Bit(s1), Bit(s2);
// cout << v << endl;
return ;
}
if (two(y) & s0) {
dfs(s0, s1, s2, y + 1, v);
return ;
}
if (y + 3 <= m) {
if (!((s0 >> y) & 7)) {
// ***
// *
if (!(two(y) & s1)) {
dfs(s0, s1 | two(y), s2, y + 3, v);
}
// ***
// *
if (!(two(y + 2) & s1)) {
dfs(s0, s1 | two(y + 2), s2, y + 3, v);
}
}
// *
// ***
if (!((s1 >> y) & 7)) {
dfs(s0, s1 | (7 << y), s2, y + 1, v);
}
}
// *
// ***
if (y >= 2 && !((s1 >> (y - 2)) & 7)) {
dfs(s0, s1 | (7 << (y - 2)), s2, y + 1, v);
}
if (y + 2 <= m) {
if (!(two(y + 1) & s0)) {
// **
// *
// *
if (!(two(y) & s1) && !(two(y) & s2)) {
dfs(s0, s1 | two(y), s2 | two(y), y + 2, v);
}
// **
// *
// *
if (!(two(y + 1) & s1) && !(two(y + 1) & s2)) {
dfs(s0, s1 | two(y + 1), s2 | two(y + 1), y + 2, v);
}
}
// *
// *
// **
if (!(two(y) & s1) && !((s2 >> y) & 3)) {
dfs(s0, s1 | two(y), s2 | (3 << y), y + 1, v);
}
}
// *
// *
// **
if (y > 0 && !(two(y) & s1) && !((s2 >> (y - 1)) & 3)) {
dfs(s0, s1 | two(y), s2 | (3 << (y - 1)), y + 1, v);
}
}
int main(int argc, char *argv[])
{
int T;
cin >> T;
Rep(Ca, T) {
cin >> n >> m;
memset(b, 0, sizeof(b));
Rep(i, n) {
string s;
cin >> s;
Rep(j, m) if (s[j] == '#') b[i] |= two(j);
}
memset(f[!cur], 0, sizeof(f[!cur]));
f[!cur][two(m) - 1][two(m) - 1] = 1;
for (int lv = 0; lv < n + 1; lv++, cur = !cur) {
// cout << "lv: " << lv << endl;
memset(f[cur], 0, sizeof(f[cur]));
Rep(s0, two(m)) Rep(s1, two(m))
if (f[!cur][s0][s1])
dfs(s0, s1, b[lv], 0, f[!cur][s0][s1]);
}
cout << f[!cur][two(m) - 1][0] << endl;
}
return 0;
}
In Java :
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
private static final int MOD = 1000000007;
private static final int[][] pieceMasks = new int[][] { {0,7,1,4}, {-2,2,-1,2,0,3},
{0,1,1,7}, {0,3,1,1,2,1},
{-1,4,0,7}, {0,1,1,1,2,3},
{0,7,1,1}, {0,3,1,2,2,2}};
private int numCols, numRows;
private int[] startState;
private HashMap<String, Long> dp;
Solution(String[] grid, int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
dp = new HashMap<String, Long>();
int[] start = new int[numCols];
for (int i = 0; i < numCols; i++) {
start[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < grid.length; i++) {
String row = grid[i];
for (int j = 0; j < row.length(); j++) {
if (row.charAt(j) == '.') {
start[j] = start[j] ^ (1 << i);
}
}
}
startState = start;
}
private boolean isFilled(int[] state) {
for (int i: state) {
if (i < Integer.MAX_VALUE) { return false; }
}
return true;
}
private int[] addShape(int[] shape, int[] state, int col, int row) {
int[] output = state.clone();
for (int i = 0; i < shape.length; i+=2) {
output[col+shape[i]] = output[col+shape[i]] | (shape[i+1] << row);
}
return output;
}
private boolean willShapeFit(int[] shape, int[] state, int col, int row) {
for (int i = 0; i < shape.length; i+=2) {
int colIdx = col + shape[i];
if (colIdx < 0 || colIdx >= numCols) { return false; }
if ((state[colIdx] & (shape[i + 1] << row)) != 0) {
return false;
}
}
return true;
}
private int[] nextEmpty(int[] state, int row, int col) {
int[] output = null;
while (row < numRows) {
if ((state[col] & (1 << row)) == 0) {
return new int[] {row, col};
}
row = (col + 1 == numCols) ? row + 1 : row;
col = (col + 1) % numCols;
}
return output;
}
private long helper(int[] state, int row, int col) {
String stateString = Arrays.toString(state);
if (dp.get(stateString) != null) { return dp.get(stateString); }
long output = 0;
for (int[] shape : pieceMasks) {
if (willShapeFit(shape, state, col, row)) {
int[] nextState = addShape(shape, state, col, row);
int[] nextIdx = nextEmpty(nextState, row, col);
if (nextIdx == null) {
output += 1;
}
else {
output += helper(nextState, nextIdx[0], nextIdx[1]);
}
}
}
dp.put(Arrays.toString(state), output);
return output % MOD;
}
public long solve() {
int[] empty = nextEmpty(startState, 0, 0);
return (empty == null) ? 1 : helper(startState, empty[0], empty[1]);
}
public static void main(String args[] ) throws Exception {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t > 0) {
int numRows = scanner.nextInt();
int numCols = scanner.nextInt();
String[] grid = new String[numRows];
Pattern p = Pattern.compile("[.#]+");
for (int i = 0; i < numRows; i++) {
grid[i] = scanner.next(p);
}
Solution solution = new Solution(grid, numRows, numCols);
System.out.println(solution.solve());
t--;
}
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
void solve1(int cas,int bit,int m2,int m3);
void solve2(int row,int m);
int c[3][8]={
{ 1, 1, 1, 1, 2, 2, 3, 3},
{ 3, 3, 1, 1, 1, 1, 1, 1},
{ 0, 0, 2, 2, 1, 1, 0, 0}
};
int o[3][8]={
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 2, 0, 0, 0,-1, 0,-2},
{ 0, 0, 0, 1, 0,-1, 0, 0}
};
int *count,**dp1;
long long **dp2;
char *table;
int main(){
int T,N,M,i,j,k,m;
char str[10];
count=(int*)malloc(300*sizeof(int));
dp1=(int**)malloc(300*sizeof(int*));
for(i=0;i<300;i++)
dp1[i]=(int*)malloc(1000*sizeof(int));
dp2=(long long**)malloc(20*sizeof(long long*));
for(i=0;i<20;i++)
dp2[i]=(long long*)malloc(70000*sizeof(long long));
table=(char*)malloc(20*sizeof(char));
for(i=0;i<300;i++)
count[i]=0;
for(i=0;i<256;i++)
solve1(i,7,0,0);
scanf("%d",&T);
while(T--){
for(i=0;i<20;i++)
for(j=0;j<70000;j++)
dp2[i][j]=-1;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++){
scanf("%s",str);
table[i]=-1;
for(j=0,k=1;j<M;j++,k<<=1)
if(str[j]=='.')
table[i]^=k;
}
m=((((int)table[N-1])&((1<<8)-1))<<8)|(((int)table[N-2])&((1<<8)-1));
solve2(N-1,m);
printf("%lld\n",dp2[N-1][m]);
}
return 0;
}
void solve1(int cas,int bit,int m2,int m3){
int i=1<<bit,j,ls,t,tm2,tm3;
while(bit>=0 && (i&cas)){
bit--;
i>>=1;
}
if(bit==-1){
dp1[cas][count[cas]++]=(m2<<8)|m3;
return;
}
for(j=0;j<8;j++){
tm3=m3;
if(c[2][j]>0){
t=-1;
t=(t>>c[2][j])<<c[2][j];
t=~t;
ls=bit-o[2][j]-c[0][j]+1;
if(ls<0)
continue;
t<<=ls;
if(t&m3 || t>=256)
continue;
tm3=m3|t;
}
t=-1;
t=(t>>c[1][j])<<c[1][j];
t=~t;
ls=bit-o[1][j]-c[0][j]+1;
if(ls<0)
continue;
t<<=ls;
if(t&m2 || t>=256)
continue;
tm2=m2|t;
t=-1;
t=(t>>c[0][j])<<c[0][j];
t=~t;
ls=bit-c[0][j]+1;
if(ls<0)
continue;
t<<=ls;
if(t&cas || t>=256)
continue;
solve1(cas,bit-c[0][j],tm2,tm3);
}
return;
}
void solve2(int row,int m){
int i,m2,m3,t2;
long long ans=0;
if(row==1)
for(i=0;i<count[m>>8];i++){
m2=dp1[m>>8][i]>>8;
m3=dp1[m>>8][i]&((1<<8)-1);
t2=m&((1<<8)-1);
if(m3 || m2&t2)
continue;
if((m2|t2)==(1<<8)-1)
ans=(ans+1)%MOD;
}
else
for(i=0;i<count[m>>8];i++){
m2=dp1[m>>8][i]>>8;
m3=dp1[m>>8][i]&((1<<8)-1);
t2=m&((1<<8)-1);
if(m3&table[row-2] || m2&t2)
continue;
m2=((m2|t2)<<8)|(m3|(((int)table[row-2])&((1<<8)-1)));
if(dp2[row-1][m2]==-1)
solve2(row-1,m2);
ans=(ans+dp2[row-1][m2])%MOD;
}
dp2[row][m]=ans;
return;
}
In Python3 :
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]))
View More Similar Problems
Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →