NYOJ10,skiing

NYOJ10,skiing

skiing

描述

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
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

來源

經典題目

import java.util.Arrays;
import java.util.Scanner;


public class NYOJ10_ieayoio {
	public static int [][]map;
	public static int [][]f;
	public static int []dx={0,1,0,-1,0};
	public static int []dy={0,0,-1,0,1};
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int t=input.nextInt();
		while (t-->0){
			int n=input.nextInt();
			int m=input.nextInt();
			map=new int [n+5][m+5];
			for (int i=0;imap[xx][yy]){
				int comway=1+dfs(xx,yy);
				if (f[x][y]map[x+dx[1]][y+dy[1]]) flag=true;
		if (map[x][y]>map[x+dx[2]][y+dy[2]]) flag=true;
		if (map[x][y]>map[x+dx[3]][y+dy[3]]) flag=true;
		if (map[x][y]>map[x+dx[4]][y+dy[4]]) flag=true;
		return flag;
	}

}

挺高興的一直感覺沒把握做的題，做了兩天，經過調試通過樣例後，沒想到一次性提交就過了

方法就是深搜，不過就是加了一個數組f[x][y]，來保存點(x,y)可滑到最低點的最長距離,dfs(x,y)用來深搜這個距離,若f[x][y]已存在，則將函數的值直接返回為f[x][y],

isnoway函數式來判斷點(x,y)是否可以向更低點滑行