首页 > 代码库 > BNUOJ 23905 滑雪
BNUOJ 23905 滑雪
滑雪
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on UESTC. Original ID: 130964-bit integer IO format: %lld Java class name: Main
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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
第一行是一个整数t,代表case数。
对于每一个case:
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
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
Sample Output
25
Source
SHTSC 2002
解题:我以前总是担心这样搜索,会不会搜回来,其实这个是按从高到低的,严格从高到底,所有不会搜回来的!
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define INF 0x3f3f3f3f15 using namespace std;16 int mp[110][110],r,c,dp[110][110];17 int dfs(int x,int y,int h) {18 static int dir[4][2] = {0,-1,0,1,-1,0,1,0};19 if(x < 0 || x >= r || y < 0 || y >= c || mp[x][y] >= h) return 0;20 if(dp[x][y]) return dp[x][y];21 int theMax = 1;22 for(int i = 0; i < 4; i++){23 int tx = x+dir[i][0];24 int ty = y+dir[i][1];25 int temp = dfs(tx,ty,mp[x][y])+1;26 if(temp > theMax) theMax = temp;27 }28 return dp[x][y] = theMax;29 }30 int main() {31 int ans = 1;32 scanf("%d %d",&r,&c);33 for(int i = 0; i < r; i++){34 for(int j = 0; j < c; j++){35 scanf("%d",mp[i]+j);36 dp[i][j] = 0;37 }38 }39 for(int i = 0; i < r; i++){40 for(int j = 0; j < c; j++){41 ans = max(ans,dfs(i,j,INF));42 }43 }44 cout<<ans<<endl;45 return 0;46 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。