http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
【題意簡述】
給出矩陣地圖，值為高度，找一條最長的高度遞減的路徑。
【分析】
動態(tài)記憶遞歸搜索，在遞歸最底層求出最優(yōu)解，記錄，自底向上的方式求出最優(yōu)解。
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};
// 判斷下標(biāo)是否越界
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
飛翔天使 閱讀(1642)
評論(0) 編輯 收藏 所屬分類:
poj