2023-02-11:给你两个整数 m 和 n 。构造一个 m x n 的网格,其中每个单元格最开始是白色

2023-02-11:给你两个整数 m 和 n 。构造一个 m x n 的网格,其中每个单元格最开始是白色,
请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色,
涂色方案需要满足:不存在相邻两个单元格颜色相同的情况。
返回网格涂色的方法数。因为答案可能非常大。
返回 对 109 + 7 取余 的结果。
1 <= n <= 1000。
1 <= m <= 5。

答案2023-02-11:

递归。

代码用rust编写。代码如下:

use std::iter::repeat;
fn main() {
    let ans3 = color_the_grid(4, 3);
    println!("ans3 = {}", ans3);
}

static MOD: i32 = 1000000007;

fn color_the_grid(m: i32, n: i32) -> i32 {
    let status = 1 << (m << 1);
    let mut dp: Vec<Vec<Vec<i32>>> = repeat(
        repeat(repeat(-1).take(status as usize).collect())
            .take(m as usize)
            .collect(),
    )
    .take(n as usize)
    .collect();
    return process(0, 0, 0, n, m, &mut dp);
}

fn process(i: i32, j: i32, s: i32, n: i32, m: i32, dp: &mut Vec<Vec<Vec<i32>>>) -> i32 {
    if i == n {
        return 1;
    }
    if j == m {
        return process(i + 1, 0, s, n, m, dp);
    }
    if dp[i as usize][j as usize][s as usize] != -1 {
        return dp[i as usize][j as usize][s as usize];
    }
    let up = (s >> (j * 2)) & 3;
    let left = if j == 0 { 0 } else { (s >> ((j - 1) << 1)) & 3 };
    let mut ans = 0;
    if up != 1 && left != 1 {
        ans += process(i, j + 1, (s ^ (up << (j * 2))) | (1 << (j * 2)), n, m, dp);
        ans %= MOD;
    }
    if up != 2 && left != 2 {
        ans += process(i, j + 1, (s ^ (up << (j << 1))) | (2 << (j << 1)), n, m, dp);
        ans %= MOD;
    }
    if up != 3 && left != 3 {
        ans += process(i, j + 1, (s ^ (up << (j << 1))) | (3 << (j << 1)), n, m, dp);
        ans %= MOD;
    }
    dp[i as usize][j as usize][s as usize] = ans;
    return ans;
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商