# 1931. Painting a Grid With Three Different Colors
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/painting-a-grid-with-three-different-colors/
## 思路
和[1349. Maximum Students Taking Exam](https://hackmd.io/pIRFwFXgQGWTbTNDPwrYDg), [1411. Number of Ways to Paint N × 3 Grid](https://hackmd.io/AKffexhVRtGqAo1_PAqr2Q)很像
但是区别在于之前是每一行写成一个mask表示三个格子用了什么颜色
但现在由于行数通常比列数小 (列数可以到1000,而行数最大到5) 所以我们为了节省空间把每一列写成一个mask

还有一个变动是我们提前存下了所有有可能的mask(相邻两个颜色不一样)
这样就不用遍历所有$3^n$个mask
否则就会TLE
## Code

class Solution {
    public int colorTheGrid(int m, int n) {
        if(m<n) return colorTheGrid(n,m);
        int mod = 1000000007;
        List<Integer> candidate = new ArrayList<>();
        
        for(int i=0; i<Math.pow(3,n); i++){
            if(selfCheck(i,n)) candidate.add(i);
        }
        long[] dp = new long[candidate.size()];
        Arrays.fill(dp,1);
        for(int i=1; i<m; i++){
            long[] temp = dp.clone();
            for(int j=0; j<candidate.size(); j++){
                int mask = candidate.get(j);
                dp[j] = 0;
                for(int k=0; k<candidate.size(); k++){
                    int prevMask = candidate.get(k);
                    if(checkDiffRow(mask,prevMask,n)){
                        dp[j] = (temp[k]+dp[j])%mod;
                    }
                }
            }
        }
        long ans = 0;
        for(int i=0; i<candidate.size(); i++){
            ans = (ans+dp[i])%mod;
        }
        return (int)ans;
    }
    private boolean selfCheck(int mask, int n){
        int prev = -1;
        for(int i=0; i<n; i++){
            int curr = mask%3;
            if(prev==curr) return false;
            prev = curr;
            mask /= 3;
        }
        return true;
    }
    private boolean checkDiffRow(int m1, int m2, int n){
        for(int i=0; i<n; i++){
            if(m1%3==m2%3) return false;
            m1/=3;
            m2/=3;
        }
        return true;
    }
}