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