Learning On the Way

1931. Painting a Grid With Three Different Colors

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 color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.

A detailed version

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        from collections import defaultdict
        MOD = 1000000007

        table = ['123', '132', '213', '231', '312', '321']

        def createByTable(s):
            for t in table:
                res = []
                for c in s:
                    res.append(t[ord(c) - ord('1')])
                yield ''.join(res)

        def compatible(s1, s2):
            for c1, c2 in zip(s1, s2):
                if c1 == c2:
                    return False
            return True

        if m == 1:
            return 3 * 2 ** (n - 1) % MOD

        elif m == 2:
            patterns = ['12']
            # return 6 * 3 ** (n - 1) % MOD

        elif m == 3:
            patterns = ['121', '123']

            # a121, a123 = 6, 6
            # for i in range(n - 1):
            # a121, a123 = a121 * 3 + a123 * 2, a121 * 2 + a123 * 2
            # return (a121 + a123) % mod

        elif m == 4:
            patterns = ['1212', '1213', '1231', '1232']

        elif m == 5:
            patterns = ['12121', '12123', '12131', '12132', '12312', '12313', '12321', '12323']

        d = defaultdict(int)

        for p in patterns:
            d[p] = 6

        stringsByPattern = defaultdict(list)
        for p in patterns:
            stringsByPattern[p] = list(createByTable(p))
            # print(p, stringsByPattern[p])

        N = len(patterns)

        matrix = [[0] * N for _ in range(N)]

        for i in range(N):
            for j in range(N):
                pat1 = stringsByPattern[patterns[i]][0]
                for pat2 in stringsByPattern[patterns[j]]:
                    if compatible(pat1, pat2):
                        matrix[i][j] += 1

        for i in range(n - 1):
            dcopy = d.copy()
            d.clear()
            for j in range(N):
                for i in range(N):
                    d[patterns[j]] += matrix[i][j] * dcopy[patterns[i]]

        return sum(d.values()) % MOD

A concise version

class Solution: 
    def colorTheGrid(self, m, n): 
        C = [c for c in product([0,1,2], repeat = m) if all(x!=y for x,y in zip(c, c[1:]))] 
        MOD, dp, d = 10**9 + 7, Counter(C), defaultdict(list) 
        for c1, c2 in product(C, C): 
            if all(x != y for x, y in zip(c1, c2)): 
                d[c1].append(c2) 
        for _ in range(n-1): 
            dp2 = Counter() 
            for c1 in C: 
                for c2 in d[c1]: 
                    dp2[c2] = (dp2[c2] + dp[c1]) % MOD 
            dp = dp2 
        return sum(dp.values()) % MOD