http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
【题意简述】
给出矩阵地图，值为高度，找一条最长的高度递减的路径。
【分析】
动态记忆递归搜索，在递归最底层求出最优解，记录，自底向上的方式求出最优解。
import java.util.*;
import java.io.*;
public class poj_1088
{
public static int R,C;
public static int[][] m=new int[100][100];
public static int[][] Count=new int[100][100];
public static int[] dx={0,0,1,-1};
public static int[] dy={1,-1,0,0};
// 判断下标是否越界
public static boolean is_ok(int i,int j){
if(i>=0 && i<R && j>=0 && j<C)
return true;
else
return false;
}
public static int dp(int loci,int locj){
int i,tempi,tempj,temp,max=0;
if(Count[loci][locj]!=0)
return Count[loci][locj];
for(i=0;i<4;i++){
tempi=loci+dx[i];
tempj=locj+dy[i];
if(is_ok(tempi,tempj) && m[tempi][tempj]<m[loci][locj]){
temp=dp(tempi,tempj);
max=max>temp?max:temp;
}
}
Count[loci][locj]=max+1;
return max+1;
}
public static void main(String rgs[]) throws Exception
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int i,j,max=0,temp;
R = cin.nextInt();
C = cin.nextInt();
for(i=0;i<R;i++){
for(j=0;j<C;j++)
m[i][j] = cin.nextInt();
Arrays.fill(Count[i],0);
}
for(i=0;i<R;i++){
for(j=0;j<C;j++){
temp=dp(i,j);
max=max>temp?max:temp;
}
}
System.out.println(max);
}
}posted on 2009-09-01 15:57
飞翔天使 阅读(1632)
评论(0) 编辑 收藏 所属分类:
poj