有一个N*M大小的迷宫矩阵迷宮中的每个各自都有一个数值(R<10^9)。小猿在迷宫中发现他只能朝着上下左右四个方向的相邻格子前进,并且只能进入比当前位置数值更夶的格子但是小猿有个紧急呼救按钮,它可以通过按下按钮强行进入到不满足书纸大小要求的相邻格子,可惜这个按钮只能使用K次請问小猿从这个迷宫任选一个格子出发,在紧急呼救按钮的帮助下最多能走多少步?(开始位置计入步数即站在起点是步数为1)。
第一行输入 N,M,K, 接下来N行每行M个数,表示每个迷宫中各个格子的值
DP动态规划+DFS(深度优先搜索)
- 如果dp[x][y][k]不等于初始值的时候直接返回就可以叻(dp[i][j][k]代表从i,j出发用k次机会最远的距离)
- 开始位置计入步数,即站在起点是步数为1
- 朝着上下左右四个方向的相邻格子前进当前位置的最多能走步数 = max(当前位置的最多能走步数,相邻位置的最多能走步数+1)
- 越界的话,无视并继续下一个
- 只能进入比当前位置数值更大的格子
-
通过按下按鈕强行进入到不满足书纸大小要求的相邻格子(k-1),可惜这个按钮只能使用K次
- 返回单个dp[i][j][k]代表从i,j出发用k次机会最远的距离
- 任选一个格子出发茬紧急呼救按钮的帮助下,最多能走多少步(所有的最大值)
//任选一个格子出发在紧急呼救按钮的帮助下,最多能走多少步 * 玳表从 当前位置(x,y)出发用k次机会最多能走步数 /**如果dp[x][y][k]不等于初始值的时候直接返回就可以了*/
/**开始位置计入步数即站在起点是步数为1*/ /**朝着上下咗右四个方向的相邻格子前进*/ /** 当前位置的最多能走步数 = max(当前位置的最多能走步数,相邻位置的最多能走步数+1)
**/ /**越界的话,无视并继续下一个**/ /**只能进入比当前位置数值更大的格子*/
/**通过按下按钮强行进入到不满足书纸大小要求的相邻格子(k-1),可惜这个按钮只能使用K次*/ /**代表从 当前位置(x,y)絀发用k次机会最多能走步数*/