From 87badbaba07e4cd13c2281e15c96ccf2dd8b3106 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 17 May 2025 23:15:29 -0600 Subject: 1931. painting a grid with three different colours --- painting_grid_three_colours.py | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) create mode 100644 painting_grid_three_colours.py (limited to 'painting_grid_three_colours.py') diff --git a/painting_grid_three_colours.py b/painting_grid_three_colours.py new file mode 100644 index 0000000..d33b1d8 --- /dev/null +++ b/painting_grid_three_colours.py @@ -0,0 +1,42 @@ +# 1931. Painting a Grid With Three Different Colors +from collections import Counter + +""" +you are given two integers 'm' and 'n'. consider an 'm x n' grid where each +cell is initially white. you can paint each cell red, green, or blue. all +cells must be painted. return the number of ways to colour the grid with no +two adjacent cells having the same colour. since the answer can be very +large, return it modulo 10^9+7. +""" + + +class Solution(object): + def colorTheGrid(self, m, n): + """ + :type m: int + :type n: int + :rtype: int + """ + dp = {(1 << (2 * m)) - 1: 1} + mod = 10**9 + 7 + for i in range(m * n - 1, -1, -1): + copy = Counter() + x, y = divmod(i, m) + for j in dp: + valid = {0, 1, 2} + if y < m - 1: + valid.discard(j >> (2 * m - 2)) + if x < n - 1: + valid.discard(j & 3) + for k in valid: + new = (j >> 2) + (k << (2 * m - 2)) + copy[new] = (copy[new] + dp[j]) % mod + dp = copy + return sum(dp.values()) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.colorTheGrid(m=1, n=1)) + print(obj.colorTheGrid(m=1, n=2)) + print(obj.colorTheGrid(m=5, n=5)) -- cgit v1.2.3