1411 给N*3网格涂色的方案数

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

给你网格图的行数 n 。

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

示例 1：

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

示例 2：

输入：n = 2
输出：54

示例 3：

输入：n = 3
输出：246

示例 4：

输入：n = 7
输出：106494

示例 5：

输入：n = 5000
输出：30228214

解法一：

暴力遍历

class Solution:
    def numOfWays(self, n: int) -> int:
        res = [[None for _ in range(4)] for _ in range(n+1)]
        def test(i,j,res,num):
            if i == n+1:
                num += 1
                return num

            for k in range(3):
                if (k==res[i-1][j]) or (k==res[i][j-1]):
                    continue
                res[i][j] = k
                # print(res)
                if j<3:
                    num = test(i,j+1,res,num)
                else:
                    num = test(i+1,1,res,num)
            return num
        return test(1,1,res,0)