Day2-N-滑雪-POJ1088
2024-10-08 15:26:12
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25 分析:记忆化搜索+DFS即可,代码如下:
const int maxm = ;
const int dx[] = {-, , , };
const int dy[] = {, , -, }; int r, c, d[maxm][maxm], G[maxm][maxm]; bool inside(int x,int y) {
return x >= && x < r && y >= && y < c;
} int dfs(int x,int y) {
if(d[x][y])
return d[x][y];
d[x][y] = ;
for(int i = ; i < ; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if(inside(nx,ny) && G[x][y] < G[nx][ny]) {
d[x][y] = max(d[x][y], dfs(nx, ny) + );
}
}
return d[x][y];
} int main() {
scanf("%d%d", &r, &c);
for (int i = ; i < r; ++i) {
for (int j = ; j < c; ++j)
scanf("%d", &G[i][j]);
}
int res = ;
for (int i = ; i < r; ++i) {
for (int j = ; j < c; ++j) {
if(!d[i][j])
res = max(res, dfs(i, j));
}
}
printf("%d\n", res);
return ;
}
最新文章
- 点评前端开发工具cortex安装使用方法
- Tastypie与Backbone交互
- golang github.com/go-sql-driver/mysql 遇到的数据库,设置库设计不合理的解决方法
- Oracle- 正则表达式查询
- MVC简单分页(未实现无刷新分页)
- JS浏览器关闭时清空cookie
- 使用SC命令时注意事项
- BZOJ 2875: [Noi2012]随机数生成器( 矩阵快速幂 )
- VS多平台开发
- @Autowired 和 @Resource
- (转载)基于Bash命令行的百度云上传下载工具
- 剑指offer(纪念版)读书笔记【实时更新】
- vuetify | vue | 文件上传组件 | file | upload | form input[type=";file";]
- Hadoop伪分布式的搭建
- Python selenium巧用Javascript脚本注入解决按钮点选问题
- css 文本超出2行就隐藏并且显示省略号
- 分析JVM GC Dump 工具
- 实验吧ctf题库web题wp
- Python 爬虫编码格式问题 gb2312转换utf8
- linux内核分析 1、2章读书笔记
热门文章
- IPv4地址被用光,IPv6将接手
- 吴裕雄 python 神经网络——TensorFlow训练神经网络:卷积层、池化层样例
- Nexus-配置vPC 实验二
- Update(Stage4):sparksql:第1节 SparkSQL_使用场景_优化器_Dataset &; 第2节 SparkSQL读写_hive_mysql_案例
- CSS - 表格细线边框
- 复盘实战营一期毕业典礼----HHR计划----以太入门课--第一课
- java模式之单例
- 基于Modelsim的视频流仿真
- TensorFlow基础一(Symbolic Operation)
- postInvalidate 解决View.GONE,没有刷新的问题