鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

dfs(深度优先搜素)poj1088

来源:互联网 作者:佚名 时间:2015-09-25 05:38
题目链接:http://poj.org/problem?id=1088 题目解析:要求出最长的降序子序列,遍历四个方向记忆化搜索; #includecstdio#includeiostream#includealgorithmusing namespace std;int dp[101][101],a[101][101];int n,i,j,k,m;int dfs(int x,int y){if(dp[x]

题目链接:http://poj.org/problem?id=1088

题目解析:要求出最长的降序子序列,遍历四个方向记忆化搜索;

 

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[101][101],a[101][101];
int n,i,j,k,m;
int dfs(int x,int y){
	if(dp[x][y]!=0) return dp[x][y];
	if(x==0||x==n+1||y==0||y==m+1) return 0;
	int maxn=0;
	if(a[x-1][y]<a[x][y]) maxn=max(maxn,dfs(x-1,y));
	if(a[x+1][y]<a[x][y]) maxn=max(maxn,dfs(x+1,y));
	if(a[x][y-1]<a[x][y]) maxn=max(maxn,dfs(x,y-1));
	if(a[x][y+1]<a[x][y]) maxn=max(maxn,dfs(x,y+1));
	dp[x][y]=maxn+1;
	return dp[x][y];
}
int main(){
	while(cin>>n>>m){
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				cin>>a[i][j];
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				dfs(i,j);
		int ans=-1;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				if(dp[i][j]>ans)
					ans=dp[i][j];
		cout<<ans<<endl;	
	}
	return 0;
}

网友评论
<