//解1
#include<stdio.h>
int n,m;
int map[100][100]; //地图存储
int lon[100][100]; //滑行最长距离存储
int dir[4][2]= {1,0,0,1,-1,0,0,-1}; //四个方向的坐标变化
bool inmap(int x,int y) //判断当前要访问节点(x,y)是否在地图内
{
if(x>=0&&x<n&&y>=0&&y<m)
return true;
else
return false;
}
int dfs(int x,int y)
{
int nx,ny,i;
int max1=1;
if(lon[x][y]>1) //要是该点已经处理过了,取值不是初值,直接返回该点的值即可
return lon[x][y];
for(i=0; i<4; i++) //对四个可能能滑行的方向分别搜索
{
nx=x+dir[i][0];
ny=y+dir[i][1];
if(inmap(nx,ny)&&map[x][y]>map[nx][ny]) //该点在地图内,该点值比上一点的值小
{
lon[x][y]=dfs(nx,ny)+1; //上一点的最大滑行距离=max{四个方向相邻点的最大滑行距离}+1
if(lon[x][y]>max1) //记录四个方向相邻点对该点的影响,该点搜索的最大值
max1=lon[x][y];
}
}
lon[x][y]=max1; //记录最大值,便于下次使用
return max1; //返回最大值
}
int main()
{
int i,j;
int longest,k;
scanf("%d",&k);
// while(k--)//NYOJ 10
// {
//以下为POJ1088
scanf("%d%d",&n,&m);
longest=1;
for(i=0; i<n; i++)
for(j=0; j<m; j++)
{
scanf("%d",&map[i][j]);
lon[i][j]=1; //所有点的滑行最长长度初始化为1,只有自身
}
for(i=0; i<n; i++) //对地图上的每个点进行动归+搜索,求出该点能滑行的最长长度
{
for(j=0; j<m; j++)
{
int t=dfs(i,j);
longest=longest>t?longest:t; //记录滑行长度的最长值
}
}
printf("%d\n",longest); //输出所有点滑行长度的最长值
// }
return 0;
}
/*解2
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
#define M 105
int X[]={-1,1,0,0},Y[]={0,0,-1,1};
int map[M][M],len[M][M];
int r,c;
bool Ok(int i,int j){
if(i>0&&i<=r&&j>0&&j<=c) return true;
return false;
}
int DFS(int x,int y){
int temp,k;
if(len[x][y]>0) return len[x][y];
for(k=0;k<4;k++){
if(Ok(x+X[k],y+Y[k])&&(map[x+X[k]][y+Y[k]]>map[x][y])){
temp=DFS(x+X[k],y+Y[k])+1;
if(temp>len[x][y]) len[x][y]=temp;
}
}
return len[x][y];
}
int main()
{
int i,j,ans,temp;
while(scanf("%d %d",&r,&c)==2){
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
scanf("%d",&map[i][j]);
ans=-INF;
memset(len,0,sizeof(len));
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
temp=DFS(i,j);
if(ans<temp) ans=temp;
}
}
printf("%d\n",ans+1);
}
return 0;
}
*/
数据结构 动态规划DP (POJ 1088 && NYOJ 10),布布扣,bubuko.com
数据结构 动态规划DP (POJ 1088 && NYOJ 10)
原文:http://blog.csdn.net/zzucsliang/article/details/22475979