1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

本题在 n×mn \times mn×m 网格上统计从唯一全局最小值格子走到唯一全局最大值格子的路径条数。每一步只能走向四邻域中海拔严格更高的格子,且高度差不超过 maxDiff。路径上每个格子最多访问一次;由于海拔沿步严格递增,图中不存在环路,从任意格子沿合法边走向更高海拔构成有向无环图(DAG),因此可用 记忆化搜索(DFS + memo) 自终点(或自起点)统计路径数。

具体做法:

  1. 扫描网格得到全局最小值、最大值及其坐标 (sx,sy)(s_x,s_y)(sx​,sy​)、(tx,ty)(t_x,t_y)(tx​,ty​)(题面保证各唯一)。
  2. 定义 dfs(i,j):从 (i,j)(i,j)(i,j) 出发,沿「海拔上升且步长 ∈(0,maxDiff]\in(0,\text{maxDiff}]∈(0,maxDiff]」的四连通边走到终点的路径数。
  3. 边界:若 (i,j)(i,j)(i,j) 为终点,返回 111;否则对四个方向尝试扩展,累加合法邻居的 dfs 结果。

P4726.勇攀数字高峰(200分)

    1000ms Tried: 202 Accepted: 54 Difficulty: 6 所属公司 : 华为od
    算法与标签>DFS

题目描述

你在给定的数字地形图中寻找登山路径,数字代表当前位置的海拔高度,要求从最低海拔出发,不断攀登,最终到达最高山峰。你需要寻找所有满足条件的登山路径。 地图已经保证最低海拔和最高山峰都只有一个。

路径条件

  • 登山规则:路径上的海拔必须严格递增
  • 移动限制:可以向上下左右 444 个方向移动
  • 路径限制:路径必须从最低海拔开始,到最高海拔结束
  • 访问控制:每个地点只能走一次
  • 高度差限制:每一步的攀登高度差必须大于 000,小于等于指定值

输入格式

输入一个二维数组表示的海拔图,维度为 n×mn \times mn×m(2≤n,m≤102 \le n,m \le 102≤n,m≤10),每个元素都是一个整数 xxx 输入一个整数参数表示单步最大允许的高度差

输出格式

输出满足条件的登山路径的数量

示例1

输入

[[1,2],[3,5]],2

输出

1

说明

起点:最低点坐标 (0,0)(0,0)(0,0),海拔高度 111 终点:最高点坐标 (1,1)(1,1)(1,1),海拔高度 555 单步最大高度差:222 可行路径: 路径 111:(0,0),(1,0),(1,1)(0,0), (1,0), (1,1)(0,0),(1,0),(1,1)

示例2

输入

[[4,3],[3,2]],1

输出

2

说明

起点:最低点坐标 (1,1)(1,1)(1,1),海拔高度 222 终点:最高点坐标 (0,0)(0,0)(0,0),海拔高度 444 单步最大高度差:111 可行路径: 路径 111:(1,1),(0,1),(0,0)(1,1), (0,1), (0,0)(1,1),(0,1),(0,0) 路径 222:(1,1),(1,0),(0,0)(1,1), (1,0), (0,0)(1,1),(1,0),(0,0)

示例3

输入

[[1,3],[3,4]],1

输出

0

说明

起点:最低点坐标 (0,0)(0,0)(0,0),海拔高度 111 终点:最高点坐标 (1,1)(1,1)(1,1),海拔高度 444 单步最大高度差:111 可行路径:000

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 2, 77ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?