Algorithms & Data Structures : Leetcode 1931. Painting a Grid With Three Different Colors

題目:

Painting a Grid With Three Different Colors - LeetCode

一題有趣的題目，看了別人的 write up 才了解要怎麼寫 QQ。

題目大綱:

共有三種顏色：R, G, B，相鄰的格子不能填上相同的顏色。
請問所有顏色的組合數目。

一開始的錯誤想法:

在想 state 的時候，我一直想要抓出規律，並且想要記錄每一"格"的狀態。沒有想過可以一次紀錄一整個欄 ( column ) 的狀態。

看完大神的想法所寫的程式碼:

一列列的進行遍尋。
在每一列遍尋 1024 種可能，並檢查

1. 我們只使用 01, 10, 11 來代表顏色，不能有 00 — check_input
2. 相鄰的顏色不可相同。 — check_color

我的程式碼有個問題：會重複檢查同一欄的顏色，應該要像大神的 code 那樣，一格格遍尋，遍尋完一欄再存狀態，才不會重複檢查。

#define M 1000000007
class Solution {
public:
    
    // 每兩 bit 代表三種顏色的選擇
    // 不使用 0
    // 三種顏色分別為 01, 10, 11
    bool check_input(int input, int m) {
        
        for(int i = 0;i < m;i++) {
            if((input & 3) == 0) {
                return false;   
            }
            input = input >> 2;
        }
        
        return true;
    }
    
    bool check_color(int prev_color, int now_color, int m) {
        
        int up = 0;
        int left = 0;
        int now = 0;
        
        for(int i = 0;i < m;i++) {
            left = prev_color & 3;
            now  = now_color & 3;
            
            if(left == now || up == now) {
                return false;   
            }
            up = now;
            prev_color = prev_color >> 2;
            now_color = now_color >> 2;   
        }
        
        return true;
    }
    
    int dfs(int col, int prev_color, vector<vector<int>> &dp, int m) {
        
        int ret = 0;
        if(dp[col][prev_color] != 0) {
            return dp[col][prev_color];   
        }
        
        if(col == 0) {
            //所有 color 都可以，只須注意上下相鄰的格子有沒有顏色重複
            for(int i = 0;i < dp[0].size();i++) {
                if(check_input(i, m) && check_color(0, i, m)) {
                    ret += dfs(col + 1, i, dp, m);
                    ret %= M;
                }
            }
            
            dp[col][0] = ret;
        } else if(col == dp.size() - 1){
            // 僅遍尋顏色
            for(int i = 0;i < dp[0].size();i++) {
                if(check_input(i, m) && check_color(prev_color, i, m)) {
                    ret++;
                    ret %= M;
                }
            }
            
            dp[col][prev_color] = ret;
        } else {
            //檢查與前一個顏色相比，是否可行
            for(int i = 0;i < dp[0].size();i++) {
                if(check_input(i, m) && check_color(prev_color, i, m)) {
                    ret += dfs(col + 1, i, dp, m);   
                    ret %= M;
                }
            }
            dp[col][prev_color] = ret;
        }
        
        return ret;
    }
    
    int colorTheGrid(int m, int n) {
        
        if(n == 1) {
            int ret = 3;
            m--;
            while(m > 0) {
                ret = ret << 1;
                m--;
            }
            return ret;
        }
        
        vector<vector<int>> dp = vector<vector<int>>(n, vector<int>((1 << (m * 2)), 0));
           
        return dfs(0, 0, dp, m);
    }
};

大神的想法與程式碼:

i : 列， 0≤ i <5
j : 欄， 0≤ j < 1000
cur : 目前這一欄的顏色 ( bitmask )
prev : 上一個欄的顏色 ( bitmask )

是一格格的遍尋，dp[column][color of prev column ( bitmask )];

int dp[1001][1024] = {};
int colorTheGrid(int m, int n, int i = 0, int j = 0, int cur = 0, int prev = 0) {
    // 這一欄已經拜訪完了，朝下一個欄位邁進
    if (i == m)
        return colorTheGrid(m, n, 0, j + 1, 0, cur);
    // 整張 table 遍尋完了，整張 table 的顏色組合都沒問題 ( 相鄰的格子皆為不同顏色 )，可以 return 1。
    if (j == n)
        return 1;
    // 這一欄已經被拜訪過了，直接 return
    if (i == 0 && dp[j][prev])
        return dp[j][prev];
    // up : 找出上面那一格的顏色，0 代表沒顏色
    // left : 找出左邊那一格的顏色， 0 代表沒塗色
    int res = 0, up = i == 0 ? 0 : (cur >>  ((i - 1) * 2)) & 3, left  = prev >> (i * 2) & 3;
    // 遍尋三種顏色，沒問題的話就將此顏色填入 cur ，並遍尋同一欄位的下一列。
    for (int k = 1; k <= 3; ++k)
        if (k != left && k != up)
            res = (res + colorTheGrid(m, n, i + 1, j, cur + (k << (i * 2)), prev)) % 1000000007;
    // 該欄已經遍尋結束，將此欄遍尋的結果存在 dp[欄位][上一個欄位的顏色 ( bitmask )]
    if (i == 0)
        dp[j][prev] = res;
    return res;
}

Reference

大神題解