We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Brick Tiling

Brick Tiling

Problem
Submissions
Leaderboard
Discussions

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.

Sample Input

3  
2 4  
....  
....  
3 3  
...  
.#.  
...  
2 2  
##  
##

Sample Output

2  
4  
1

Explanation

NOTE:
If all points in the grid are blocked the number of ways is 1, as in the last sample testcase.

Author

HackerRank

Difficulty

Hard

Max Score

60

Submitted By

1650

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy