[C++] hash map for DP with bitmasking column index and colored column, explained
The idea is to use 0b100, 0b010 and 0b001 respectively for R, G and B colors. For example, a column of size m = 5 with RGRBG code would give an integer : 0b100 
The idea is to use `0b100`, `0b010` and `0b001` respectively for R, G and B colors. For example, a column of size `m = 5` with RGRBG code would give an integer : `0b100 010 100 010 001`. To know in one pass how to spot the right column with its index, I shift the index beyond the 32 first bits used for the colors. There are two steps :\n* First I precompute all the valid colors that I store in a vector.\n* Then I perform a DFS from each one of those colors and stop the recursion as soon as the previous column was already obtained so far, looking in the DP data structure. the DP gives for a certain pair (column, index) the number of solutions that start from that colored column at that column index.\n```\nclass Solution {\npublic:\n    int colorTheGrid(int m, int n) {\n    \n        unordered_map<long, int> dp;     \n        vector<int> validCols;  \n        \n        generateCols(m, validCols, 0, 0);\n        \n        return getNbSols(validCols, 0, 0, n, dp);\n    }\n    \n    /**\n    * compute the number of valid solutions for the grid, performing a DFS\n    * from each of the precomputed valid colors (3 * 2 ^ (m - 1) possible permutations).\n    * Use the hash map to reuse the dynamically computed solutions.\n    */\n    int getNbSols(vector<int>& validCols, int prevCol, long colIdx, int n, unordered_map<long, int>& dp) {\n        if(colIdx == n) return 1;\n        int ans = 0;\n        for(int col : validCols) {\n            if(not (col & prevCol)) { // check horizontal crossing, not processing adjacent colors\n               if(dp.find((colIdx << 32) + col) == dp.end()) {\n                    dp[(colIdx << 32) + col] = getNbSols(validCols, col, colIdx + 1, n, dp); \n                }\n                ans = (ans + dp[(colIdx << 32) + col]) % MOD;\n            }\n        }\n        return ans % MOD;\n    }\n    \n    /**\n    * generate all valid color permutations for a column, i.e those who\n    * does not have two same adjacent colors\n    */\n    void generateCols(int m, vector<int>& validCols, int curCol, int rowIdx) {\n        if(rowIdx == m) {validCols.push_back(curCol); return;}\n        for(int c = 0b001; c <= 0b100; c *= 2) {\n            int prev_c = 0;\n            if(rowIdx) prev_c = curCol >> 3 * (rowIdx - 1) & 0b111;\n            if(prev_c != c) { // check vertical crossing, not processing adjacent colors\n                generateCols(m, validCols, c << 3 * rowIdx | curCol, rowIdx + 1);\n            }\n        }\n    }\n\nprivate:\n    int MOD = 1e9 + 7;\n};\n```
['C']