2023-02-11:给你两个整数 m 和 n 。构造一个 m x n 的网格,其中每个单元格最开始是白色, 请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有
2023-03-07 09:08:50 时间
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;
}
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的