Easy solution in c++
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Generateing all possible permutation using (m^3)\n2. Finding all permutation that co
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. Generateing all possible permutation using (m^3)\n2. Finding all permutation that could be promoted to\na. For example, 12 -> 21, 23 and etc.\n3. Using DP to record the value of transferring\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS, DP\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m^3^2) for finding all qualified promotion\nO(n * m^3^2) for moving stage by stage\n    Since m is very small, we could ignore m as a constant.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    void createPermu(vector<int>& permu, int m, int current){\n        if (m == 0) permu.push_back(current);\n        else{\n            int lastDigit = current % 10;\n            createPermu(permu, m - 1, current * 10 + (lastDigit) % 3 + 1);\n            createPermu(permu, m - 1, current * 10 + (lastDigit + 1) % 3 + 1);\n        }\n    }\n\n    bool check(int a, int b){\n        while (a > 0){\n            if (a % 10 == b % 10) return false;\n            a /= 10;\n            b /= 10;\n        }\n        return true;\n    }\n\n    int colorTheGrid(int m, int n) {\n        int mod(1e9 + 7);\n        vector<int> permu;\n        createPermu(permu, m - 1, 1);\n        createPermu(permu, m - 1, 2);\n        createPermu(permu, m - 1, 3);\n\n        unordered_map<int, vector<int>> allowedNext;\n        for (auto &a: permu) for (auto &b: permu) if (check(a, b)) allowedNext[a].push_back(b);\n        unordered_map<int, vector<unsigned int>> dp;\n        for (auto &permuToNext: allowedNext){\n            dp[permuToNext.first].resize(n, 0);\n            dp[permuToNext.first][0] = 1;\n        }\n        for (int i = 1; i < n; ++i){\n            for (auto &permuToNext: allowedNext){\n                for (auto &next: permuToNext.second){\n                    (dp[next][i] += dp[permuToNext.first][i - 1]) %= mod;\n                }\n            }\n        }\n        int ans(0);\n        for (auto &pos: dp){\n            (ans += pos.second[n - 1]) %= mod;\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Combinatorics', 'C++']