题解 UVA10285 最长的滑雪路径 Longest Run on a Snowboard
2024-09-07 05:06:59
Solution
就是记搜嘛。
搞一个二维数组记录一下当前的最长滑雪路径,其他和普通 dfs 没什么两样。
向 \(4\) 个方向搜索,如果高度符合就 \(+1\) 。
多测要注意数组初始化。
具体见代码。
Code
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[105][105],b[105][105],maxx,t;
int dx[4]={-1,1,0,0},
dy[4]={0,0,-1,1};
string name;
#define max(x,y) x>y?x:y
inline int dfs(int x,int y)
{
if(b[x][y])
return b[x][y];//判重
b[x][y]=1;
for(int i=0;i<4;++i)//向四个方向去
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||yy<1||xx>n||yy>m)
continue;//判边界
if(a[xx][yy]>=a[x][y])
continue;//判高低
b[x][y]=max(b[x][y],dfs(xx,yy)+1);
}
return b[x][y];
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)//多测
{
memset(b,0,sizeof(b));
memset(a,0,sizeof(a));//初始化
cin>>name>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>a[i][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
b[i][j]=dfs(i,j);//搜索+存储
maxx=max(maxx,b[i][j]);
}
cout<<name<<": "<<maxx<<"\n";
maxx=0;
}
return 0;
}
最新文章
- Docker与CI持续集成/CD
- SqlHelper c#
- [Docker]Docker快速上手学习笔记
- VC++ 将IP字符串转为 DWORD值
- [原]如何用Android NDK编译FFmpeg
- java 打包过程及如何使用第三方jar包
- TCPIP三次握手详情
- java 实现数据结构之队列
- Windows PowerShell ISE
- Java核心技术卷二部分笔记
- python 零散记录(七)(下) 新式类 旧式类 多继承 mro 类属性 对象属性
- openerp 中如何方便对搜索时间段
- 使用 Nginx 来反向代理多个 NoderCMS
- PhotoShop基本工具 -- 移动工具
- linux下mysql root密码忘记修改方法
- Form开发:字段关系-消息-快速编码-参数和系统变量
- springcloud之hystrix熔断器-Finchley.SR2版
- 导出zabbix监控数据
- CF987B - High School: Become Human
- Codeforces Round #428 (Div. 2)A,B,C
热门文章
- LuoguU72177 火星人plus (逆康拓展开)
- Windows 查看端口占用并关闭
- Go语言 WaitGroup 详解
- ACM模式细节
- React报错之You provided a&#160;`checked`&#160;prop to a form field
- NOI 2019 省选模拟赛 T1【JZOJ6082】 染色问题(color) (多项式,数论优化)
- LibTorch 自动微分
- 【debug技巧】jstat:虚拟机统计信息监视器
- Django 聚合查询 分组查询 F与Q查询
- Stream流式计算