[Python] Column-by-Column Counting
The general idea of this approach is that since columns are small, m <= 5, we can think about counting the number of ways as we fill out the grid left to right,
The general idea of this approach is that since columns are small, `m <= 5`, we can think about counting the number of ways as we fill out the grid left to right, column by column. Specifically, once we fill out a column, we no longer care about the colors in any other columns to the left of it. This way, we can just keep track of how many colorings there are that "end" in a specific column coloring. When we want to add another column (move "right"), we simply figure out which column-colorings are valid from each current column-coloring, and then update.\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        valid = []\n        for r in itertools.product(*[(0,1,2) for _ in range(m)]):\n            if all(r[i] != r[i+1] for i in range(m-1)):\n                valid.append(r)\n        g = {i:set() for i in range(len(valid))}\n        for i in range(len(valid)):\n            for j in range(i+1,len(valid)):\n                if all(valid[i][x] != valid[j][x] for x in range(m)):\n                    g[i].add(j)\n                    g[j].add(i)\n        s=[1 for _ in range(len(valid))]\n        for _ in range(n-1):\n            ns=[0 for _ in range(len(valid))]\n            for i in range(len(valid)):\n                for j in g[i]:\n                    ns[j] = (ns[j] + s[i]) % 1000000007\n            s=ns\n        return sum(s) % 1000000007\n```\nThis only works because m is small: at m=5, there\'s only 48 valid column-colorings, which means 48<sup>2</sup> = 2304 transitions (although it\'s smaller since we preprocess it into a "graph", where an edge between two column-colorings indicates that they can be adjacent to each other), which we only need to repeat n<=1000 times.\n\nAfter that we just sum up the number of valid colorings ending in each configuration and we have our answer. The efficiency of this approach is bounded by O(n * 3<sup>2m</sup>) ~ 59M ops here, but in practice it\'s faster because there are significantly fewer than 3^m valid column-colorings, and the preprocessed graph isn\'t too dense.
[]