Description

Submission

class Solution {
    bool checkOk(int s, int t, int m) {
        for(int i = 0; i < m; ++i) {
            if(s % 3 == t % 3) return false;
            s /= 3;
            t /= 3;
        }
        return true; 
    }
public:
    int colorTheGrid(int m, int n) {
        const long long M = 1e9 + 7;
        vector<int> validStates;

        for(int state = 0; state < pow(3, m); ++state) {
            int prevDigit = -1;
            int curState = state;
            bool flag = true;
            for(int i = 0; i < m; ++i, curState /= 3) {
                int digit = curState % 3;
                if(digit == prevDigit) {
                    flag = false;
                    break;
                }
                prevDigit = digit;
            }
            if(flag) validStates.push_back(state);
        }
        int sz = validStates.size();
        vector<long long> dp(sz, 1);

        for(int i = 1; i < n; ++i) {
            vector<long long> dp2(sz, 0);
            for(int j = 0; j < sz; ++j) {
                for(int k = 0; k < sz; ++k) {
                    if(checkOk(validStates[j], validStates[k], m)) {
                        dp2[k] = (dp2[k] + dp[j]) % M;
                    }
                }
            }
            dp = dp2;
        }
        
        long long ret = 0;

        for(auto x: dp) {
            ret += x;
        }

        return ret % M;
    }
};