931. 用三种不同颜色为网格涂色

931. 用三种不同颜色为网格涂色

题目链接：931. 用三种不同颜色为网格涂色

代码如下：

class Solution {
public:int colorTheGrid(int m, int n) {vector<int> pow3(m);pow3[0] = 1;for (int i = 1;i < m;i++) {pow3[i] = pow3[i - 1] * 3;}vector<int> valid;for (int color = 0;color < pow3[m - 1] * 3;color++) {bool ok = true;for (int i = 1;i < m;i++) {if (color / pow3[i] % 3 == color / pow3[i - 1] % 3) {//相邻的颜色相同ok = false;break;}}if (ok) {valid.push_back(color);}}int nv = valid.size();vector<vector<int>> nxt(nv);for (int i = 0;i < nv;i++) {for (int j = 0;j < nv;j++) {bool ok = true;for (int k = 0;k < m;k++) {if (valid[i] / pow3[k] % 3 == valid[j] / pow3[k] % 3) {//相邻颜色相同ok = false;break;}}if (ok) {nxt[i].push_back(j);}}}vector memo(n, vector<int>(nv, -1));auto dfs = [&](auto&& dfs, int i, int j)->int {if (i == 0) {return 1;// 找到了一个合法涂色方案}int& res = memo[i][j];// 注意这里是引用if (res != -1) { // 之前计算过return res;}res = 0;for (int k : nxt[j]) {res = (res + dfs(dfs, i - 1, k)) % MOD;}return res;};long long res = 0;for (int j = 0;j < nv;j++) {res += dfs(dfs,n - 1, j);}return res % MOD;}private:const int MOD = 1'000'000'007;
};