产品网站开发服务,济南建站,廊坊关键词优化,论坛做网站好吗901. 滑雪 - AcWing题库
给定一个 R 行 C 列的矩阵#xff0c;表示一个矩形网格滑雪场。
矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。
一个人从滑雪场中的某个区域内出发#xff0c;每次可以向上下左右任意一个方向滑动一个单位距离。
当然#xff0…901. 滑雪 - AcWing题库
给定一个 R 行 C 列的矩阵表示一个矩形网格滑雪场。
矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。
一个人从滑雪场中的某个区域内出发每次可以向上下左右任意一个方向滑动一个单位距离。
当然一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9在给定矩阵中一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中最长的滑行轨迹为 25−24−23−…−3−2−1沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度请你找出在该滑雪场中能够完成的最长滑雪轨迹并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行每行包含 C 个整数表示完整的二维矩阵。
输出格式
输出一个整数表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300 0≤矩阵中整数≤10000
输入样例
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输出样例
25解析
AcWing 901. 滑雪 - AcWing
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 305;
int n, m;
int h[N][N];
int f[N][N];int ax[] { 0,0,1,-1 }, ay[] { 1,-1,0,0 };int dp(int x, int y) {int v f[x][y];if (v ! -1)return v;v 1;for (int i 0; i 4; i) {int a x ax[i], b y ay[i];if (a 1 a n b 1 b m h[x][y] h[a][b])v max(v, dp(a, b) 1);}return v;
}int main() {scanf(%d%d, n, m);for (int i 1; i n; i) {for (int j 1; j m; j)scanf(%d, h[i][j]);}memset(f, -1, sizeof(f));int ans 0;for (int i 1; i n; i)for (int j 1; j m; j)ans max(ans, dp(i, j));cout ans endl;return 0;
}
