AcWing 901. 滑雪
2024-08-30 21:44:36
地址 https://www.acwing.com/problem/content/description/903/
题目描述
给定一个R行C列的矩阵,表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。
当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子:
在给定矩阵中,一条可行的滑行轨迹为24-17-2-1。
在给定矩阵中,最长的滑行轨迹为25-24-23-…-3-2-1,沿途共经过25个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数R和C。
接下来R行,每行包含C个整数,表示完整的二维矩阵。
输出格式
输出一个整数,表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300,
0≤矩阵中整数≤10000
输入样例: 输出样例:
算法1
一开始 写的常规DFS
但是在某些数据 超时。果然没那么简单
代码
#include <iostream>
#include <vector> using namespace std; const int N = ;
int n,m;
int maxlen = -;
vector<vector<int>> vv; int addx[] = {,-,,};
int addy[] = {,,,-}; void dfs(int x,int y,int len)
{
if(len > maxlen) maxlen = len; for(int i = ;i < ;i++){
int newx = x + addx[i];
int newy = y + addy[i]; if(newx >= && newx < n && newy >= && newy < m &&
vv[newx][newy] < vv[x][y])
{
dfs(newx,newy,len+);
}
}
} int main()
{
cin >> n >> m; for(int i = ; i < n;i++){
vector<int> v;
vv.push_back(v);
for(int j = ;j< m;j++){
int t =;
cin >> t;
vv[i].push_back(t);
}
} for(int i = ; i < n;i++){
for(int j = ;j < m;j++){
int len =;
dfs(i,j,len);
}
} cout << maxlen+ << endl; return ;
}
算法2
使用记忆化数组 记录每个点的最大滑动长度
遍历每个点作为起点
然后检测该点四周的点 如果可以滑动到其他的点
那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1
dp[i][j] = max(dp[i][j-1], dp[i][j+1],dp[i-1][j],dp[i+1][j])
由于滑雪是必须滑到比当前低的点 在任意一个起点的dfs中,不会存在一个点多次进入的问题
如果该点的dp[][] 不为初始化值 那么就说明计算过 不必再次计算。
按照上述公式 代码如下 AC
#include <iostream> using namespace std; const int N = ;
int R,C; int arr[N][N];
int dp[N][N]; int maxlen = -; int addx[] = {,-,,};
int addy[] = {,,,-}; int Dfs(int x,int y)
{
if(dp[x][y] != ) return dp[x][y]; for(int i = ;i < ;i++){
int newx = x + addx[i];
int newy = y + addy[i]; if(newx >= && newx < C && newy >= && newy < R &&
arr[newx][newy] < arr[x][y])
{
dp[x][y] = max(dp[x][y], Dfs(newx,newy) +);
}
}
return dp[x][y];
} int main()
{
ios::sync_with_stdio(false); cin >> R >>C; for(int i = ; i < R;i++){
for(int j=;j<C;j++){
cin >> arr[i][j];
}
} for(int i = ; i < R;i++){
for(int j = ;j< C;j++){
int len = Dfs(i,j);
maxlen = max(maxlen,len);
}
} cout << maxlen + << endl; return ;
}
最新文章
- TotoiseSVN的基本使用方法
- 微信小程序文件作用域模块引用
- MySQL安全性语言
- 3.HelloWorld
- HTML 空格的表示符号 nbsp / ensp / emsp 的区别?
- AIR 3.0针对移动设备的高性能渲染方案
- 内存泄露 Memory Leaks
- ubuntu scp
- STL采用的标准模板库
- WinAPI: GetVolumeInformation - 读取文件系统信息
- Toy Storage POJ 2398
- tf.contrib.slim arg_scope
- 23. Merge k Sorted Lists (JAVA)
- python的异步IO模块
- maven命令package、install、deploy比较
- Redis内存分析方法
- Django-基本指令
- Uploadify3.2中文提示
- BZOJ4247 : 挂饰
- Docker 常用命令与操作
热门文章
- centos 下安装rabbitmq
- Dynamics 365 Customer Engagement导入解决方案时出错:Microsoft.Crm.CrmException: Plug-in assembly does not contain the required types or assembly content cannot be updated.
- 头条小视频和西瓜视频signature签名算法
- spring为类的静态属性实现注入
- apache commons lang架包介绍
- n个数字相加
- python与数据库交互的模块pymysql
- RabbitMQ基础理解
- Oracle 11gR2中HR用户安装说明
- composer中常用命令