aboutsummaryrefslogtreecommitdiff
path: root/domino_tromino_tiling.c
diff options
context:
space:
mode:
Diffstat (limited to 'domino_tromino_tiling.c')
-rw-r--r--domino_tromino_tiling.c31
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
+}