| ||||||||||
| 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