题目描述

你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

样例

输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

输入：n = 2
输出：54

输入：n = 3
输出：246

输入：n = 7
输出：106494

输入：n = 5000
输出：30228214

提示：

• n == grid.length
• grid[i].length == 3
• 1 <= n <= 5000

算法分析

状态压缩 + 递推
此题与 Acwing 98 费解的开关 方法类似

• 1、用0,1,2分别表示3种不同的颜色，枚举出所有的情况即用6位的二进制进行表示，如000110,分成3份即00,01,10,注意：11(即3)的这种情况不存在，需要去掉
• 2、若当前行的方案数确定时，下一行的方案数也跟着确定，因此可以通过递推的思想，先枚举第1行的所有状态，通过第1行推出第2行，再通过第2行推出第3行…直到最后一行
• 3、f[i][j]表示在第i行，j状态的总方案数，枚举上一行的所有状态，若上一行的某种状态k能够转移到当前行j的状态，则f[i][j] += f[i - 1][k]，最后将最后一行的所有状态的方案数全部累积起来即答案所求

时间复杂度 $O(n * 64^2)$

Java 代码

class Solution {
    static int mod = 1000000000 + 7;
    //当前状态的idx位置，idx有0,1,2
    static int get(int x,int idx)
    {
        return (x >> (idx * 2)) % 4;
    }
    public int numOfWays(int n) {
        int[][] f = new int[n + 1][64];
        for(int i = 0;i < 64;i ++)
        {
            int a = get(i,0),b = get(i,1),c = get(i,2);
            if(a == 3 || b == 3 || c == 3) continue;
            if(a == b || b == c) continue;
            f[1][i] = 1;
        }
        for(int i = 2;i <= n;i ++)
        {
            for(int u = 0;u < 64;u ++)
            {
                int ua = get(u,0),ub = get(u,1),uc = get(u,2);
                if(ua == 3 || ub == 3 || uc == 3) continue;
                if(ua == ub || ub == uc) continue;
                for(int v = 0;v < 64;v ++)
                {
                    int va = get(v,0),vb = get(v,1),vc = get(v,2);
                    if(va == 3 || vb == 3 || vc == 3) continue;
                    if(va == vb || vb == vc) continue;
                    if(va == ua || vb == ub || vc == uc) continue;
                    f[i][v] = (f[i][v] + f[i - 1][u]) % mod;
                }
            }
        }
        long res = 0;
        for(int i = 0;i < 64;i ++) res = (res + f[n][i]) % mod;
        return (int)res;
    }
}