Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一个中规中矩的记忆化搜索

Posted by lhrlhr at 2014-10-30 13:46:49 on Problem 1088
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator