aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--domino_tromino_tiling.c31
-rw-r--r--domino_tromino_tiling.py34
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))