I was keen to know the algorithm to solve this problem. The formal description of the problem statement is something like this-Given N(<100) and dominoes 2x1 and 1x2 I have to find the number of different grid tilings possible. The difference here is that some cells will be blackened to denote the forbidden position.
Input:
5
01000
00010
Output:
1
The 0 in the input represents an empty cell and 1 forbidden cell. I found a similar question here Hexagonal Grid Tiling . Although there was a slight mention about solving these kinds of problem with Dynamic Programming with Bitmasks, I was unable to find any thorough explanation regarding this technique.
PS: Although I know how to solve a general grid tiling problem, say in this problem only if we are given only the empty cells then a recurrence can be formed as F(n) = F(n-1) + F(n-2), by either placing a 1x2 domino or placing two 2x1 dominoes to cover first and first two columns respectively. This can be solved iteratively or even for Large N(say > 10^7) we can use Matrix Exponentiation technique. But I am interested in knowing about the technique of solving these kinds of problems by DP+Bitmasks. Any help would be appreciated.
For i = n, n-1, ..., 1 you calculate f00 (i) = "Number of combinations to fill from column i if column i contained 0,0", f01 (i) = "Number of combinations to fill from column i if column i contained 0,1", f10 (i) = "Number of combinations to fill from column i if column i contained 1,0", f11 (i) = "Number of combinations to fill from column i if column i contained 1,1"
Obviously f00 (n) = f11 (n) = 1, f01 (n) = f10 (n) = 0.
f00 (i) if i < n: You can use one vertical tile whatever is in the next column, or two horizontal tiles if the next column is (0, 0). So if the next column is (0, 0) then the result is f00 (i + 1) + f11 (i + 1); if the next column is (0, 1), (1, 0) or (1, 1) then f00 (i) = f01, f10 or f11 (i + 1).
f10 (i) for i < n: You must use one horizontal tile. If the next column contains (0, 1) or (1, 1) then the result is 0; if the next column contains (0, 0) or (1, 0) then the result is f01 (i+1) or f11 (i+1).
f01 (i) works the same.
f11 (i) = f00, f01, f10 or f11 (i + 1) depending what's in the next column.
Solution is easily found in linear time.