leetcode1931 用三种不同颜色为网格涂色

思路：

状态压缩动态规划，使用了滚动数组优化空间。

实现：

 1 class Solution
 2 {
 3 public:
 4     bool check(int x, int y, int M)
 5     {
 6         for (int i = 0; i < M; i++)
 7         {
 8             int p = x & 3, q = y & 3;
 9             if (p == q) return false;
10             x >>= 2; y >>= 2;
11         }
12         return true;
13     }
14     int colorTheGrid(int m, int n)
15     {
16         int M = min(m, n), N = max(m, n);
17         vector<int> v;
18         int MOD = 1e9 + 7;
19         for (int i = 0; i < 1 << 2 * M; i++)
20         {
21             vector<int> tmp;
22             int s = i;
23             bool flg = true;
24             for (int j = 0; j < M; j++)
25             {
26                 if ((s & 3) == 3) { flg = false; break; }
27                 tmp.push_back(s & 3);
28                 s >>= 2;
29             }
30             if (!flg) continue;
31             for (int j = 0; j < (int)tmp.size() - 1; j++)
32             {
33                 if (tmp[j + 1] == tmp[j]) { flg = false; break; }
34             }
35             if (flg) v.push_back(i);
36         }
37         unordered_map<int, vector<int>> mp;
38         for (int i = 0; i < (int)v.size(); i++)
39         {
40             for (int j = i + 1; j < (int)v.size(); j++)
41             {
42                 int x = v[i], y = v[j];
43                 if (check(x, y, M))
44                 {
45                     if (!mp.count(i)) mp[i] = vector<int>();
46                     mp[i].push_back(j);
47                     if (!mp.count(j)) mp[j] = vector<int>();
48                     mp[j].push_back(i);
49                 }
50             }
51         }
52         int l = v.size();
53         vectorint>> dp(2, vector<int>(l, 0));
54         for (int i = 0; i < l; i++) dp[0][i] = 1;
55         for (int i = 1; i < N; i++)
56         {
57             for (int j = 0; j < l; j++)
58             {
59                 dp[i & 1][j] = 0;
60                 for (int k = 0; k < (int)mp[j].size(); k++)
61                 {
62                     int t = mp[j][k];
63                     dp[i & 1][j] = (dp[i & 1][j] + dp[i - 1 & 1][t]) % MOD;
64                 }
65             }
66         }
67         int res = 0;
68         for (int i = 0; i < l; i++) res = (res + dp[N - 1 & 1][i]) % MOD;
69         return res;
70     }
71 };