skiing
时间限制：3000 ms | 内存限制：65535 KB
难度：5
描述
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更长。事实上，这是最长的一条。
输入
第一行表示有几组测试数据，输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
后面是下一组数据；
输出
输出最长区域的长度。
样例输入
1
2
3
4
5
6
7
8
| 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
|
样例输出
第一次使用bfs居然AC了一个动态规划的题了，事实证明那个思路没有问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| /**
*
*/
package 动态规划;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @作者： gx_143
* @创建时间： 2017-4-30上午09:32:21
*/
public class T8skiing {
/**
* @param args
*/
static int h,w;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] out=new int[n];
for (int i = 0; i < out.length; i++) {
h=sc.nextInt();
w=sc.nextInt();
int[][] data=new int[h][w];
for (int j = 0; j < data.length; j++) {
for (int l = 0; l < data[0].length; l++) {
data[j][l]=sc.nextInt();
}
}
int max=0;
for (int j = 0; j < data.length; j++) {
for (int l = 0; l < data[0].length; l++) {
int re=f(data,j,l);
if(re>max)
max=re;
}
}
out[i]=max;
}
for (int i = 0; i < out.length; i++) {
System.out.println(out[i]);
}
}
static int[][] stepArr =new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
private static int f(int[][] data, int a,int b) {
int max=0;
Node node=new Node(a,b,data[a][b],1);
Queue<Node> queue=new LinkedList<Node>();
queue.add(node);
while(!queue.isEmpty()){
Node newNode=queue.poll();
if(newNode.step>max)
max=newNode.step;
for(int i=0;i<4;i++){
int x=newNode.x+stepArr[i][0];
int y=newNode.y+stepArr[i][1];
if(x>=0&&y>=0&&x<w&&y<h&&data[newNode.x][newNode.y]>data[x][y]){
Node next=new Node(x,y,newNode.sum+data[x][y],newNode.step+1);
queue.add(next);
}
}
}
return max;
}
private static class Node{
private int x;
private int y;
private int sum;
private int step;
public Node(int x,int y ,int sum,int step){
this.x=x;
this.y=y;
this.sum=sum;
this.step=step;
}
}
}
|