1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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))
|