Java | 100% faster | Generalized
This is a generalized solution of any n and any m.\n\nThe code looks complicated, but the logic is quite easy. Although the code is long, the solution has by fa
This is a **generalized** solution of any `n` and any `m`.\n\nThe code looks complicated, but the logic is quite easy. Although the code is long, the solution has by far the best performance.\n\nSay, `m = 5`. We name the color as numbers: `0, 1, 2`\n\nSteps:\n1. For each line, we have limited `patterns`, eg, `01010`, `01012`... We store the patterns in `patterns` as Strings.\n2. For each `pattern`, we record the eligible neighbors in `nexts`. Eg, for `01010`, its eligible neighbors are `10101`, `10102`...\n3. We just loop `n` times to let the count of each `pattern` roll.\n4. The final result would be the sum of all the counts, then timed by 3.\n\n\n```java\nclass Solution {\n    private int mod = 1000000007;\n    \n    private void expand(int[] list, int ind, List<String> patterns, Map<String, Integer> indices) {\n        if (ind == list.length) {\n            StringBuilder pattern = new StringBuilder();\n            for (int num : list) pattern.append(num);\n            indices.put(pattern.toString(), patterns.size());\n            patterns.add(pattern.toString());\n            return;\n        }\n        for (int candidate = 0; candidate < 3; candidate++) {\n            if (candidate != list[ind - 1]) {\n                list[ind] = candidate;\n                expand(list, ind + 1, patterns, indices);\n            }\n        }\n    }\n    \n    private void expand2D (int[] list, int[] nextList, int ind, List<String> patterns, Map<String, Integer> indices, List<Integer> next) {\n        if (ind == list.length) {\n            int offset = 3 - nextList[0];\n            StringBuilder pattern = new StringBuilder();\n            for (int num : nextList) pattern.append((num + offset) % 3);\n            next.add(indices.get(pattern.toString()));\n            return;\n        }\n        for (int candidate = 0; candidate < 3; candidate++) {\n            if (candidate != nextList[ind - 1] && candidate != list[ind]) {\n                nextList[ind] = candidate;\n                expand2D(list, nextList, ind + 1, patterns, indices, next);\n            }\n        }\n    }\n        \n    public int colorTheGrid(int m, int n) {\n\t\tif (n < m) {\n\t\t\tint temp = m;\n\t\t\tm = n;\n\t\t\tn = temp;\n\t\t}\n        // all are starting from red\n        if (m == 1) {\n            int[] paintLine = new int[n];\n            paintLine[n - 1] = 1;\n            for (int j = n - 2; j >= 0; j--) paintLine[j] = (paintLine[j + 1] * 2) % mod;\n            return (int)((long)paintLine[0] * 3 % mod);\n        }\n        \n        // get all patterns\n        List<String> patterns = new ArrayList<>();\n        Map<String, Integer> indices = new HashMap<>();\n        int[] list = new int[m];\n        list[0] = 0;\n        expand(list, 1, patterns, indices);\n        int p = patterns.size();\n        \n        if (n == 1) return 3 * p;\n        \n        // get all nexts\n        List<List<Integer>> nexts = new ArrayList<>();\n        for (int i = 0; i < p; i++) {\n            List<Integer> next = new ArrayList<>();\n            nexts.add(next);\n            String string = patterns.get(i);\n            list = new int[m];\n            for (int chi = 0; chi < m; chi++) list[chi] = string.charAt(chi) - \'0\';\n            int[] nextList = new int[m];\n            for (int candidate = 0; candidate < 3; candidate++) {\n                if (candidate != list[0]) {\n                    nextList[0] = candidate;\n                    expand2D(list, nextList, 1, patterns, indices, next);\n                }\n            }\n        }\n        \n        // calculate\n        int[] counts = new int[p];\n        Arrays.fill(counts, 1);\n        for (int round = 0; round < n - 1; round++) {\n            int[] temp = new int[p];\n            for (int pi = 0; pi < p; pi++) {\n                List<Integer> next = nexts.get(pi);\n                for (int ni : next) {\n                    temp[pi] += counts[ni];\n                    temp[pi] %= mod;\n                }\n            }\n            counts = temp;\n        }\n        \n        int res = 0;\n        for (int count : counts) {\n            res += count;\n            res %= mod;\n        }\n        return (int)((long)res * 3 % mod);\n    }\n}\n```\n\nIn the end,\n\nThere may be some solutions which predefines the neighboring relationships, that have better performances.\nThe aim of this solution is to illustrate the idea and generalize it.
[]