Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一个中规中矩的记忆化搜索#include <iostream> #include <cstring> #include <cstdio> using namespace std; int m,n,dp[105][105],a[105][105];//a用来存储图的信息 dp代表每个点的最大长度 int go[4][2] = { 1,0,-1,0,0,1,0,-1 };//方向数组 bool out(int x,int y) { if(x >= m || x < 0 || y < 0 || y >= n) return false; return true; }//判断超界函数 int dfs(int x,int y)//记忆化深搜 { if(dp[x][y] > 0) return dp[x][y];//如果这个点已经在dp表中出现了就直接返回其值不用下一步递归计算 int big = 0,tx,ty,t; for(int i = 0 ; i < 4 ; i++)//分上下左右四个方向搜索 { tx = x + go[i][0]; ty = y + go[i][1]; if( out(tx,ty) )//如果不越界 if( a[x][y] > a[tx][ty] )//并且这个要选择的点比当前点的位置低 if(big < ( t = dfs(tx,ty) ) ) big = t; //那么我们就让四个方向里最大值变为它能到的最大值 } return dp[x][y] = big+1; //并再此基础上加上这一步,也就是+1 } int main(int argc, char const *argv[]) { //freopen("in.txt","r",stdin); while(scanf("%d%d",&m,&n)!=EOF) { int ans = 0,t; memset(dp,0,sizeof(dp)); for (int i = 0; i < m; ++i) { for(int j = 0 ; j < n ; j++) scanf("%d",&a[i][j]); } for(int i = 0 ; i < m ; i++) //在每一次寻找深度的时候记录最大深度,即答案 for(int j = 0 ; j < n ; j++) { t = dfs(i,j); if(ans < t) ans = t; } printf("%d\n",ans ); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator