C++ O(n * (3^m) * f) DFS + DP
The idea is to calculate all next column states from a previous column state (3^m). Then we can DP on each column.\nEach state is compressed into an int (curr, 
The idea is to calculate all next column states from a previous column state (3^m). Then we can DP on each column.\nEach state is compressed into an int (`curr`, `pre`, `hmap`\'s key) in which each adjacent two bits indicates a choice of color (00 as white).\n`hmap` counts the number of occurances of each state.\nA minor improvement can be done by caching the genNexts results for each state but it won\'t improve complexity.\nOver all complexity is `O(n * (3^m) * f)`. `f` is the fan-out number related to `m` (average length of `nexts`) which is not large when `m = 5`.\n```\nclass Solution {\n    vector<int> nexts;\n    void genNexts(int m, int i, int curr, int pre) {\n        if (i == m) {\n            nexts.push_back(curr);\n            return;\n        }\n        int a = (pre >> (i * 2)) & 3;\n        int b = 0;\n        if (i > 0) {\n            b = curr >> ((i - 1) * 2);\n        }\n        for (int j = 1; j < 4; j++) {\n            if (j == a || j == b) {\n                continue;\n            }\n            genNexts(m, i + 1, curr | (j << (i * 2)), pre);\n        }\n    }\npublic:\n    int colorTheGrid(int m, int n) {\n        constexpr int mod = 1e9 + 7;\n        unordered_map<int, int> hmap;\n        hmap[0] = 1;\n        for (int i = 0; i < n; i++) {\n            unordered_map<int, int> hmap2;\n            for (const auto &it : hmap) {\n                nexts.clear();\n                genNexts(m, 0, 0, it.first);\n                for (int next : nexts) {\n                    hmap2[next] = (hmap2[next] + it.second) % mod;\n                }\n            }\n            hmap = hmap2;\n        }\n        int result = 0;\n        for (const auto &it : hmap) {\n            result = (result + it.second) % mod;\n        }\n        return result;\n    }\n};\n```
[]