Graph Based Approach | C++ | 100% Space & Time | Explained!
\t\tvector states;\n\t\tvoid generate(string state, char prev, int m){\n        \n\t\t\tif(m==0){\n\t\t\t\tstates.push_back(state);\n\t\t\t\treturn;\n\t\t\t}\n\
\t\tvector<string> states;\n\t\tvoid generate(string state, char prev, int m){\n        \n\t\t\tif(m==0){\n\t\t\t\tstates.push_back(state);\n\t\t\t\treturn;\n\t\t\t}\n\n\t\t\tstring colors = "RGB";\n\t\t\tfor(auto &color: colors){\n\t\t\t\tif(color!=prev)\n\t\t\t\t\tgenerate(state+color, color, m-1);\n\t\t\t}\n\n\t\t}\n\n\t\t// We use memoization to make use of the fact that the ans only depends upon\n\t\t// the current state and the number of columns left to fill.\n\t\tint dp[250][1001];\n\t\tlong long waysToFill(int u, int cols_to_fill, vector<vector<int>> &G){\n\n\t\t\tif(cols_to_fill==0) return 1;\n\t\t\telse if(dp[u][cols_to_fill]!=-1) return dp[u][cols_to_fill];\n\n\t\t\tint ways = 0;\n\t\t\tfor(auto v: G[u]){\n\t\t\t\tways = (ways + waysToFill(v, cols_to_fill-1, G)) % M;\n\t\t\t}\n\n\t\t\treturn dp[u][cols_to_fill] = ways;\n\t\t}\n\n\t\tpublic:\n\t\tint colorTheGrid(int m, int n) {\n\t\t\n\t\t\t// ** Note that m<=5 whereas n<=1000 **\n\t\t\t// First of all we Generate all the possible color combinations (states)\n\t\t\t// for a column with size m, store them into a vector \'states\'\n\t\t\t// For Eg m=3 : RGB, BGR, RBR, GBG, ...\n\t\t\t// Also, we make sure that same colors are not adjacent (See generate function)\n\t\t\tgenerate("", \'*\', m);\n\n\t\t\t// Now, we can observe that the number of possible states (color combinations) for\n\t\t\t// current column only depend upon the previous column.\n\t\t\t// So we make a graph where there is an edge from i to j if we can transition from\n\t\t\t// state[i] to state[j] ( no same index can be of same color )\n\t\t\tint numStates = states.size();\n\t\t\tvector<vector<int>> G(numStates);\n\n\t\t\tfor(int i=0;i<numStates;i++){\n\t\t\t\tfor(int j=0;j<numStates;j++){\n\n\t\t\t\t\tbool is_compatible = true;\n\t\t\t\t\tfor(int k=0;k<m;k++){\n\t\t\t\t\t\tif(states[i][k]==states[j][k]){\n\t\t\t\t\t\t\tis_compatible = false; break;\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t\tif(is_compatible)\n\t\t\t\t\t\tG[i].push_back(j);\n\n\t\t\t\t}\n\t\t\t}\n\n\t\t\t// Sum up the number of ways to make a path of length n, starting from each state (node)\n\t\t\tmemset(dp, -1, sizeof(dp));\n\t\t\tint totalWays = 0;\n\t\t\tfor(int i=0;i<numStates;i++){\n\t\t\t\ttotalWays = (totalWays + waysToFill(i, n-1, G)) % M;\n\t\t\t}\n\n\t\t\treturn totalWays;\n\n\t\t}
[]