poj1088滑雪<DP>

题意: 中文题;
思路:暴力每一个点作为起点DFS; 对于每个点比较其四周的点比较
View Code
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <stdlib.h>
 6 #include <cmath>
 7 using namespace std;
 8 int N, M;
 9 struct Node 
10 {
11     int h, l;
12 }pa[105][105];
13 int Max( int a, int b, int c, int d )
14 {
15     a=a>b?a:b;
16     a=a>c?a:c;
17     a=a>d?a:d;
18     return a;
19 }
20 int DFS( int r, int c, int t )
21 {
22     if( pa[r][c].h==-1|| t<=pa[r][c].h){// 如果小就退出 
23         return 0;
24     } 
25     if( pa[r][c].l ) return pa[r][c].l;
26     pa[r][c].l=Max( DFS( r-1, c, pa[r][c].h), DFS( r+1, c ,pa[r][c].h), DFS( r, c+1 ,pa[r][c].h), DFS(r, c-1, pa[r][c].h) )+1;
27     return pa[r][c].l;     // 与四周的点比较 
28 }
29 int main( )
30 {
31     while(scanf( "%d%d", &N, &M )!=EOF){
32         for( int i=0; i<105; ++ i){
33             for(int j=0; j<105; ++ j){
34                 pa[i][j].h=-1, pa[i][j].l=0;
35             }
36         }
37         for( int i=1; i<=N; ++ i ){
38             for( int j=1; j<=M; ++ j ){
39                 scanf( "%d", &pa[i][j].h );
40             }
41         }
42         int ans=0;
43         for( int i=1; i<=N; ++ i ){
44             for(int j=1; j<=M; ++ j){
45                 int temp=DFS( i, j, pa[i][j].h+1 );// 确保每个点能作为起点入口 
46                 ans=ans>temp?ans:temp;
47             }  
48         }
49         printf( "%d\n", ans );
50     }
51     return 0;
52 }