算法笔记_174:历届试题 地宫取宝(Java)
2024-10-19 03:36:05
目录
1 问题描述
问题描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角,出口在右下角。
小明被带到地宫的入口,国王要求他只能向右或向下行走。
走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。
请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。
输入格式
输入一行3个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。
样例输入
2 2 2
1 2
2 1
1 2
2 1
样例输出
2
样例输入
2 3 2
1 2 3
2 1 5
1 2 3
2 1 5
样例输出
14
2 解决方案
本文下面代码详解请见文末参考资料。
具体代码如下:
import java.util.Scanner; public class Main {
public static int n, m, k;
public static long MOD = 1000000007;
public static int[][] map;
public static long[][][][] visited = new long[51][51][102][13]; public long dfs(int x, int y, int num, int max) {
if(visited[x][y][num][max + 1] != -1)
return visited[x][y][num][max + 1];
if(x == n - 1 && y == m - 1) {
if(num == k)
visited[x][y][num][max + 1] = 1;
else if(num == k - 1 && max < map[x][y])
visited[x][y][num][max + 1] = 1;
else
visited[x][y][num][max + 1] = 0;
return visited[x][y][num][max + 1];
}
long result = 0;
if(x + 1 < n) { //向下移动一步
if(max < map[x][y]) {
result += dfs(x + 1, y, num + 1, map[x][y]);
result %= MOD;
}
result += dfs(x + 1, y, num, max);
result %= MOD;
}
if(y + 1 < m) { //向右移动一步
if(max < map[x][y]) {
result += dfs(x, y + 1, num + 1, map[x][y]);
result %= MOD;
}
result += dfs(x, y + 1, num, max);
result %= MOD;
}
return visited[x][y][num][max + 1] = result % MOD;
} public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
k = in.nextInt();
map = new int[n][m];
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
map[i][j] = in.nextInt();
for(int i = 0;i < 51;i++)
for(int j = 0;j < 51;j++)
for(int x = 0;x < 102;x++)
for(int y = 0;y < 13;y++)
visited[i][j][x][y] = -1;
test.dfs(0, 0, 0, -1);
System.out.println(visited[0][0][0][0]);
}
}
参考资料:
最新文章
- How to fix the conflict between ROS Python and Conda
- Python3学习(3)-高级篇
- 翻译:Angular 2 - TypeScript 5 分钟快速入门
- 关于WINDOWS命令
- 如何使用SublimeText风格的代码高亮样式 添加Zed Coding(EMMET)插件
- java科学和艺术语言 第六章 课后编程
- equals()与hashCode()方法协作约定
- 程序压力测试、性能测试AB、Webbench、Tsung
- 【ASP.NET Core快速入门】(六)配置的热更新、配置的框架设计
- Go 初体验 - 并发与锁.1 - sync.Mutex 与 sync.RWMutex
- vue ui 启动,浏览器报错Unexpected token <;
- oracle sys_guid
- Django Rest framework 之 权限
- for循环 Dictionary
- 专项测试——移动app安装包检测
- MJExtension的一些实用技巧
- BASIC-27_蓝桥杯_2n皇后问题
- node 的exports 和module
- Luogu4885 灭顶之灾
- [osgearth]Earth文件详解
热门文章
- 小程序在wxml页面中取整
- 理解PHP数组的序列化和反序列化
- HTML5学习笔记4
- Send custom commands to Mass Storage device
- php 利用fsockopen GET/POST 提交表单及上传文件
- 【Nginx】ngx_event_core_module模块
- 【spring cloud】spring cloud集成zipkin报错:Prometheus requires that all meters with the same name have the same set of tag keys.
- Selenium2+python自动化46-js解决click失效问题
- [runtime] initialize方法讲解
- Andorid之使用GMail后台偷偷发送邮件(不要干坏事噢=。 =)