1931. 用三种不同颜色为网格涂色
给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。
涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。
示例 1：
输入：m = 1, n = 1 输出：3 解释：如上图所示，存在三种可能的涂色方案。
示例 2：
输入：m = 1, n = 2 输出：6 解释：如上图所示，存在六种可能的涂色方案。
示例 3：
输入：m = 5, n = 5 输出：580986
提示：
1 <= m <= 51 <= n <= 1000原站题解
java 解法, 执行用时: 42 ms, 内存消耗: 42.2 MB, 提交时间: 2023-09-28 23:10:48
class Solution {
public int colorTheGrid(int m, int n) {
final int MOD = 1_000_000_007;
// key 为有效的 mask 值，value 为 mask 值对应的 3 进制数
Map<Integer, int[]> valid = new HashMap<>();
int maskEnd = (int)Math.pow(3, m);
// 初始化 valid
for(int mask = 0; mask < maskEnd; ++mask){
int[] color = new int[m];
int mm = mask;
// 分析三进制值，如果相邻两个值相同，则不符合要求，舍弃
boolean check = true;
for(int i = 0; i < m; ++i){
color[i] = mm % 3;
if(i > 0 && color[i-1] == color[i]) check = false;
mm /= 3;
}
if(check) valid.put(mask, color);
}
// 预处理，分析所有可能相邻的二元组，将该信息放置在 map 中
// key 值为 mask 值，value 为可与该 mask 相邻的 mask 值列表
Map<Integer, List<Integer>> adjacent = new HashMap<>();
for(Integer mask1 : valid.keySet()){
List<Integer> list = new ArrayList<>();
for(Integer mask2 : valid.keySet()){
boolean check = true;
for(int i = 0; i < m; ++i){
if(valid.get(mask1)[i] == valid.get(mask2)[i]){
check = false;
break;
}
}
if(check) list.add(mask2);
}
adjacent.put(mask1, list);
}
// 由于 dp[i][mask] 仅与 dp[i-1][mask'] 有关，因此，可以使用一维数组实现 dp
int[] dp = new int[maskEnd];
// 边界条件：dp[i][mask], i == 0 时
for(Integer mask : valid.keySet()){
dp[mask] = 1;
}
// 动态规划
for(int i = 1; i < n; ++i){
int[] tmpDp = new int[maskEnd];
for(Integer mask : valid.keySet()){
for(Integer index : adjacent.get(mask)){
tmpDp[mask] += dp[index];
tmpDp[mask] %= MOD;
}
}
dp = tmpDp;
}
int ans = 0;
for(Integer mask : valid.keySet()){
ans += dp[mask];
ans %= MOD;
}
return ans;
}
}
python3 解法, 执行用时: 380 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-28 23:10:24
'''
f[i][mask] 表示我们已经对 0,1,⋯ ,i 行进行了涂色，并且第 i 行的涂色方案对应的三进制表示为 mask 的前提下的总方案数。
'''
class Solution:
def colorTheGrid(self, m: int, n: int) -> int:
mod = 10**9 + 7
# 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
# 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）
valid = dict()
# 在 [0, 3^m) 范围内枚举满足要求的 mask
for mask in range(3**m):
color = list()
mm = mask
for i in range(m):
color.append(mm % 3)
mm //= 3
if any(color[i] == color[i + 1] for i in range(m - 1)):
continue
valid[mask] = color
# 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
adjacent = defaultdict(list)
for mask1, color1 in valid.items():
for mask2, color2 in valid.items():
if not any(x == y for x, y in zip(color1, color2)):
adjacent[mask1].append(mask2)
f = [int(mask in valid) for mask in range(3**m)]
for i in range(1, n):
g = [0] * (3**m)
for mask2 in valid.keys():
for mask1 in adjacent[mask2]:
g[mask2] += f[mask1]
if g[mask2] >= mod:
g[mask2] -= mod
f = g
return sum(f) % mod
cpp 解法, 执行用时: 72 ms, 内存消耗: 17.5 MB, 提交时间: 2023-09-28 23:08:32
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int colorTheGrid(int m, int n) {
// 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
// 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）
unordered_map<int, vector<int>> valid;
// 在 [0, 3^m) 范围内枚举满足要求的 mask
int mask_end = pow(3, m);
for (int mask = 0; mask < mask_end; ++mask) {
vector<int> color;
int mm = mask;
for (int i = 0; i < m; ++i) {
color.push_back(mm % 3);
mm /= 3;
}
bool check = true;
for (int i = 0; i < m - 1; ++i) {
if (color[i] == color[i + 1]) {
check = false;
break;
}
}
if (check) {
valid[mask] = move(color);
}
}
// 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
unordered_map<int, vector<int>> adjacent;
for (const auto& [mask1, color1]: valid) {
for (const auto& [mask2, color2]: valid) {
bool check = true;
for (int i = 0; i < m; ++i) {
if (color1[i] == color2[i]) {
check = false;
break;
}
}
if (check) {
adjacent[mask1].push_back(mask2);
}
}
}
vector<int> f(mask_end);
for (const auto& [mask, _]: valid) {
f[mask] = 1;
}
for (int i = 1; i < n; ++i) {
vector<int> g(mask_end);
for (const auto& [mask2, _]: valid) {
for (int mask1: adjacent[mask2]) {
g[mask2] += f[mask1];
if (g[mask2] >= mod) {
g[mask2] -= mod;
}
}
}
f = move(g);
}
int ans = 0;
for (int num: f) {
ans += num;
if (ans >= mod) {
ans -= mod;
}
}
return ans;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 5.4 MB, 提交时间: 2023-09-28 23:07:47
const mod int = 1e9 + 7
func colorTheGrid(m, n int) (ans int) {
m *= 2
// 预处理所有合法状态：用四进制表示颜色
valid := []int{}
outer:
for mask := 0; mask < 1<<m; mask++ {
pre := 0
for j := 0; j < m; j += 2 {
color := mask >> j & 3
if color == 0 || color == pre { // 未涂色或相邻颜色相同
continue outer
}
pre = color
}
valid = append(valid, mask)
}
// 预处理所有合法状态能转移到哪些合法状态（记录合法状态的下标）
to := make([][]int, len(valid))
for i, v := range valid {
o:
for j, w := range valid {
for k := 0; k < m; k += 2 {
if v>>k&3 == w>>k&3 { // 相邻颜色相同
continue o
}
}
to[i] = append(to[i], j)
}
}
// 滚动数组，用当前行更新下一行不同状态的方案数
dp := make([]int, len(valid))
for i := range dp {
dp[i] = 1
}
for i := 1; i < n; i++ {
tmp := dp
dp = make([]int, len(valid))
for j, dv := range tmp {
for _, t := range to[j] {
dp[t] = (dp[t] + dv) % mod
}
}
}
for _, dv := range dp {
ans += dv
}
return ans % mod
}