diff options
Diffstat (limited to 'domino_tromino_tiling.c')
-rw-r--r-- | domino_tromino_tiling.c | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/domino_tromino_tiling.c b/domino_tromino_tiling.c new file mode 100644 index 0000000..d8bd02b --- /dev/null +++ b/domino_tromino_tiling.c @@ -0,0 +1,31 @@ +// 790. Domino and Tromino Tiling +#include "leetcode.h" + +/* + * you have two types of tiles: a '2 x 1' domino shape and a tromino shape. you + * may rotate these shapes. given an integer 'n', return the number of ways to + * tile a '2 x n' board. since the answer may be very large, return it modulo + * 10^9+7. in a tiling, every square must be tiled by a tile. two tilings are + * different if and only if there are two 4-directionally adjacent cells on the + * board such that exactly one of the tilings has both squares occupied by a + * tile. + */ + +int numTilings(int n) { + static int mod = 1e9 + 7; + if (n <= 2) + return n; + int x = 1, y = 2, z = 5, m; + for (int i = 4; i <= n; ++i) { + m = (2LL * z + x) % mod; + x ^= y ^= x ^= y; + y ^= z ^= y ^= z; + z ^= m ^= z ^= m; + } + return z; +} + +int main() { + printf("%d\n", numTilings(3)); // expect: 5 + printf("%d\n", numTilings(1)); // expect: 1 +} |