diff options
author | Jack Sangdahl <[email protected]> | 2025-05-17 23:15:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-17 23:15:29 -0600 |
commit | 87badbaba07e4cd13c2281e15c96ccf2dd8b3106 (patch) | |
tree | ceb97f38b7a69211175f4bb25c4b707c29f4bd5d /painting_grid_three_colours.py | |
parent | 2304d32820d403740108de84125059c623686fc9 (diff) | |
download | leetcode-87badbaba07e4cd13c2281e15c96ccf2dd8b3106.tar.gz leetcode-87badbaba07e4cd13c2281e15c96ccf2dd8b3106.zip |
1931. painting a grid with three different colours
Diffstat (limited to 'painting_grid_three_colours.py')
-rw-r--r-- | painting_grid_three_colours.py | 42 |
1 files changed, 42 insertions, 0 deletions
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)) |