UVA 10285 记忆化搜索

2019-11-06 09:09:06

字体：大中小

来源：转载

供稿：网友

题意

在一个整数矩阵中找一条严格递减的最长路，求最长路的长度。

题解

记忆化搜索，记录每个点严格递减的最长路长度即可。

代码

#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int dp[110][110],mp[110][110];int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};int r,c;int dfs(int x,int y){ int& ans=dp[x][y]; if(ans!=0) return ans; bool flag=false; for(int i=0;i<4;i++){ int a=x+dir[i][0]; int b=y+dir[i][1]; if(a>=0&&b>=0&&a<r&&b<c&&mp[x][y]>mp[a][b]){ ans=max(ans,dfs(a,b)+1); flag=true; } } if(flag==false) return 1; return ans;}int main(){ int kase; scanf("%d",&kase); for(int ks=1;ks<=kase;ks++){ memset(dp,0,sizeof(dp)); char name[100]; scanf("%s",name); scanf("%d%d",&r,&c); for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ scanf("%d",&mp[i][j]); } } for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ dfs(i,j); } } int slen=strlen(name); for(int i=0;i<slen;i++) PRintf("%c",name[i]); int maxnum=0; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ maxnum=max(maxnum,dp[i][j]); } } printf(": %d/n",maxnum); } return 0;}

上一篇：Hive基本语法操练

下一篇：Palindrome Partitioning