Concept

雖然是Hard，但其實概念不難，難度介於medium~hard，比較要小心的是可能要先做預處理，不然有可能TLE。
在做本題前可以先參考1411. Number of Ways to Paint N × 3 Grid，基本上是一樣的概念。
每一row都是一個狀態，我們只需要從row[1]開始，記錄對於前一row的狀態中所有的可能，最後再將row[n]所的狀態做加總，即可得到答案。

Steps

Step 1: 記錄每一row合法的所有組合

先假設m = 5, 我們預處理每一row的可能組合，就是3^5種，那在這3^5之中又有多少合法的組合呢?
可以用簡單的暴力法求出，並存在vector<int> type中。
如何儲存?
3^5種的話，我們用三進位去代表填色的情況
例如:
120,010, 130… 都代表合法的塡色情況。

Step 2: 在組合中求出關係

在vector<int> type中，我們可以枚舉出所有type[i]與type[j]的關係
如果type[i]與type[j]合法，則存在 related[i][j] = 1

Step 3: DP

因為row[1]可以填入任何type，所以dp[1][0~type_cnt] = 1
我們再分別對row[1~n]做處理即可。
dp[i][j] += dp[i-1][k], k ∈ related[i][k] = 1

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


class Solution {
public:
    int colorTheGrid(int m, int n) {
        vector<int> type;
        // step 1
        for(int i = 0; i < pow(3, m); i++){
            int prev = -1;
            int temp = i;
            for(int j = 0; j < m; j++){
                int curr =  temp % 3;
                if(prev == curr) break;
                prev = curr;
                temp /= 3;
                if(temp == 0 && j == m - 1){
                    type.push_back(i);
                }
            }
        }
        // step 2
        int type_cnt = type.size();
        vector<vector<int>> related(type_cnt, vector<int>(type_cnt));
        for(int i = 0; i < type_cnt; i++){
            for(int j = 0; j < type_cnt; j++){
                int temp_a = type[i];
                int temp_b = type[j];
                for(int k = 0; k < m; k++){
                    if(temp_a % 3 == temp_b % 3){
                        break;
                    }
                    temp_a /= 3;
                    temp_b /= 3;
                    if(k == m - 1){
                        related[i][j] = 1;
                    }
                }
            }
        }
        // step3
        vector<vector<int>> dp(n + 1, vector<int>(type_cnt));
        for(int i = 0; i < type_cnt; i++){
            dp[1][i] = 1;
        }
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < type_cnt; j++){
                for(int k = 0; k < type_cnt; k++){
                    if(related[j][k]){
                        dp[i][j] += dp[i-1][k];
                        dp[i][j] %= 1000000007;
                    }
                }
            }
        }
        int count = 0;
        for(int i = 0; i < type_cnt; i++){
            count += dp[n][i];
            count %= 1000000007;
        }
        return count;
    }
};

LeetCode 1931. Painting a Grid With Three Different Colors