P1434 [SHOI2002] 滑雪
P1434 [SHOI2002] 滑雪 - 洛谷
题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为24 - 17 - 16 - 1 (从24开始，在1结束)。当然25 - 24 - 23 - … - 3 - 2 - 1更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数R和列数C。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
输入输出样例
| 输入#1 | 输出#1 |
|---|---|
| 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 |
说明/提示
对于100%的数据，1≤R,C≤100。
思路：
dfs(tx, ty) + 1 的含义
当从点 (x, y) 可以滑向点 (tx, ty) 时（即满足高度递减条件，也就是 a[x][y] > a[tx][ty]，其中 a 数组存储各点的高度），从点 (x, y) 出发经过点 (tx, ty) 继续滑行的路径长度就是 dfs(tx, ty) + 1。这里的 + 1 代表从点 (x, y) 滑到点 (tx, ty) 这一步。
代码：
#include <bits/stdc++.h>
using namespace std;
int R, C, a[105][105], mem[105][105];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 正确的记忆化搜索：计算以 (i,j) 为起点的最长滑坡长度
int dfs(int x, int y)
{if(mem[x][y] != -1)return mem[x][y];mem[x][y] = 1;for(int k = 0 ; k < 4 ; k++){int tx = x + dx[k];int ty = y + dy[k];if(tx >= 1 && tx <= R && ty >= 1 && ty <= C && a[x][y] > a[tx][ty]){mem[x][y] = max(mem[x][y],dfs(tx,ty) + 1); } }return mem[x][y];
}int main()
{cin >> R >> C;for (int i = 1; i <= R; i++){for(int j = 1 ; j <= C ; j++){cin >> a[i][j];}}memset(mem,-1,sizeof(mem));int ans = -1;for (int i = 1; i <= R; i++){for(int j = 1 ; j <= C ; j++){ans = max(ans,dfs(i,j));}}cout << ans;return 0;
}