1411. 给 N x 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
提示：
n == grid.lengthgrid[i].length == 31 <= n <= 5000原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-21 23:28:45
func numOfWays(n int) int {
if n == 1 {
return 12
} else if n == 2 {
return 54
}
pre := []int{30, 24}
moVal := 1000000007
for i := 3; i <= n; i++ {
p1 := pre[0]*3%moVal + pre[1]*2%moVal
p2 := pre[0]*2%moVal + pre[1]*2%moVal
pre[0] = p1
pre[1] = p2
}
return (pre[0] + pre[1]) % moVal
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-21 23:28:16
const Mod int = 1e9 + 7
var matrix = [...]int{2, 2, 2, 3}
func Multi(a, b [4]int) [4]int { // 矩阵乘法
return [4]int {
(a[0] * b[0] + a[1] * b[2]) % Mod,
(a[0] * b[1] + a[1] * b[3]) % Mod,
(a[2] * b[0] + a[3] * b[2]) % Mod,
(a[2] * b[1] + a[3] * b[3]) % Mod,
}
}
func Power(n int) [4]int { // 快速幂计算
bases := [][4]int{matrix}
for i := 1; 1 << i <= n; i ++ {
bases = append(bases, Multi(bases[i - 1], bases[i - 1]))
}
result := [4]int{1, 0, 0, 1}
i := 0
for n > 0 {
if n & 1 == 1 {
result = Multi(result, bases[i])
}
n >>= 1
i += 1
}
return result
}
func numOfWays(n int) int {
m := Power(n - 1)
return 6 * (m[0] % Mod + m[1] % Mod + m[2] % Mod + m[3] % Mod) % Mod
}
java 解法, 执行用时: 1 ms, 内存消耗: 37.7 MB, 提交时间: 2023-09-21 23:27:21
public class Solution {
private static final int MOD = 1000000007;
public int numOfWays(int n) {
if (n == 0) {
return 0;
}
//每层的涂色可以分成ABA和ABC两类
long ABA = 6;
long ABC = 6;
for (int i = 2; i <= n; i++) {
//本层的每个ABA类 -> 下层演化为3个ABA+2个ABC
//本层的每个ABC类 -> 下层演化为2个ABA+2个ABC
ABC = 2 * (ABA + ABC) % MOD;
ABA = (ABC + ABA) % MOD;
}
return (int) ((ABA + ABC) % MOD);
}
}
python3 解法, 执行用时: 804 ms, 内存消耗: 18.5 MB, 提交时间: 2023-09-21 23:25:51
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9 + 7
# 预处理出所有满足条件的 type
types = list()
for i in range(3):
for j in range(3):
for k in range(3):
if i != j and j != k:
# 只要相邻的颜色不相同就行
# 将其以十进制的形式存储
types.append(i * 9 + j * 3 + k)
type_cnt = len(types)
# 预处理出所有可以作为相邻行的 type 对
related = [[0] * type_cnt for _ in range(type_cnt)]
for i, ti in enumerate(types):
# 得到 types[i] 三个位置的颜色
x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3
for j, tj in enumerate(types):
# 得到 types[j] 三个位置的颜色
y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3
# 对应位置不同色，才能作为相邻的行
if x1 != y1 and x2 != y2 and x3 != y3:
related[i][j] = 1
# 递推数组
f = [[0] * type_cnt for _ in range(n + 1)]
# 边界情况，第一行可以使用任何 type
f[1] = [1] * type_cnt
for i in range(2, n + 1):
for j in range(type_cnt):
for k in range(type_cnt):
# f[i][j] 等于所有 f[i - 1][k] 的和
# 其中 k 和 j 可以作为相邻的行
if related[k][j]:
f[i][j] += f[i - 1][k]
f[i][j] %= mod
# 最终所有的 f[n][...] 之和即为答案
ans = sum(f[n]) % mod
return ans
java 解法, 执行用时: 22 ms, 内存消耗: 41.2 MB, 提交时间: 2023-09-21 23:25:36
class Solution {
static final int MOD = 1000000007;
public int numOfWays(int n) {
// 预处理出所有满足条件的 type
List<Integer> types = new ArrayList<Integer>();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.add(i * 9 + j * 3 + k);
}
}
}
}
int typeCnt = types.size();
// 预处理出所有可以作为相邻行的 type 对
int[][] related = new int[typeCnt][typeCnt];
for (int i = 0; i < typeCnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types.get(i) / 9, x2 = types.get(i) / 3 % 3, x3 = types.get(i) % 3;
for (int j = 0; j < typeCnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types.get(j) / 9, y2 = types.get(j) / 3 % 3, y3 = types.get(j) % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
int[][] f = new int[n + 1][typeCnt];
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < typeCnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < typeCnt; ++j) {
for (int k = 0; k < typeCnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j] != 0) {
f[i][j] += f[i - 1][k];
f[i][j] %= MOD;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < typeCnt; ++i) {
ans += f[n][i];
ans %= MOD;
}
return ans;
}
}
cpp 解法, 执行用时: 124 ms, 内存消耗: 12.5 MB, 提交时间: 2023-09-21 23:24:59
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numOfWays(int n) {
// 预处理出所有满足条件的 type
vector<int> types;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push_back(i * 9 + j * 3 + k);
}
}
}
}
int type_cnt = types.size();
// 预处理出所有可以作为相邻行的 type 对
vector<vector<int>> related(type_cnt, vector<int>(type_cnt));
for (int i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
for (int j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
vector<vector<int>> f(n + 1, vector<int>(type_cnt));
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
for (int k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] += f[i - 1][k];
f[i][j] %= mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < type_cnt; ++i) {
ans += f[n][i];
ans %= mod;
}
return ans;
}
};