diff options
author | Jack Sangdahl <[email protected]> | 2025-05-04 19:30:19 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-04 19:30:19 -0600 |
commit | 8613fd28cfba0f76c4bf7266ba268fcbc5830a52 (patch) | |
tree | d911356034adc63b6776a59dbaadba3f9d5cd00e | |
parent | 6b424046413c73adb95d28c96e36de69e43140cd (diff) | |
download | leetcode-8613fd28cfba0f76c4bf7266ba268fcbc5830a52.tar.gz leetcode-8613fd28cfba0f76c4bf7266ba268fcbc5830a52.zip |
-rw-r--r-- | domino_tromino_tiling.c | 31 | ||||
-rw-r--r-- | domino_tromino_tiling.py | 34 |
2 files changed, 65 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 +} diff --git a/domino_tromino_tiling.py b/domino_tromino_tiling.py new file mode 100644 index 0000000..bd1c25e --- /dev/null +++ b/domino_tromino_tiling.py @@ -0,0 +1,34 @@ +# 790. Domino and Tromino Tiling + +""" +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. +""" + + +class Solution(object): + def numTilings(self, n): + """ + :type n: int + :rtype: int + """ + mod = 10**9 + 7 + if n <= 2: + return n + f_prev, g_prev, f_prev2, g_prev2 = 2, 2, 1, 1 + for i in range(3, n + 1): + filled = f_prev + f_prev2 + 2 * g_prev2 + gap = f_prev + g_prev + f_prev2, f_prev, g_prev2, g_prev = f_prev, filled, g_prev, gap + return f_prev % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.numTilings(n=3)) + print(obj.numTilings(n=1)) |