http://poj.org/problem?id=1088
一道中文题,这道题如果不限时的话,是个简单的搜索,但限时的话,就要用记忆化搜索
所谓记忆化搜索就是对每一次搜索的结果进行记录,然后之后的如果需要使用到这次搜索的结果的话,就可以直接使用,不需要再去搜索,可以减少很多时间
#include <stdio.h>
#include <iostream>
#include <string.h> using namespace std;
int cub[][];
bool jud[][];
int dis[][]; int m,n,max1,x,y,ans; int dfs(int i,int j){
if(cub[i-][j]<cub[i][j]){
if(!jud[i-][j]) { //这个就是我的记忆化搜索,把以前搜索到的结果,直接使用就可以。
ans+=dis[i-][j];
if(ans>dis[x][y]) dis[x][y]=ans;
ans-=dis[i-][j];
}
else {
ans++;
dfs(i-,j);
if(ans>dis[x][y]) dis[x][y]=ans;
ans--;
}
}
if(cub[i+][j]<cub[i][j]){
if(!jud[i+][j]) {
ans+=dis[i+][j];
if(ans>dis[x][y]) dis[x][y]=ans;
ans-=dis[i+][j];
}
else {
ans++;
dfs(i+,j);
if(ans>dis[x][y]) dis[x][y]=ans;
ans--;
}
}
if(cub[i][j-]<cub[i][j]){
if(!jud[i][j-]) {
ans+=dis[i][j-];
if(ans>dis[x][y]) dis[x][y]=ans;
ans-=dis[i][j-];
}
else {
ans++;
dfs(i,j-);
if(ans>dis[x][y]) dis[x][y]=ans;
ans--; }
}
if(cub[i][j+]<cub[i][j]){
if(!jud[i][j+]) {
ans+=dis[i][j+];
if(ans>dis[x][y]) dis[x][y]=ans;
ans-=dis[i][j+];
}
else {
ans++;
dfs(i,j+);
if(ans>dis[x][y]) dis[x][y]=ans;
ans--; }
}
jud[x][y]=false; //每一个搜索后,对那个那个搜索后的点进行标记
return ;
}
int main(){
scanf("%d%d",&m,&n);
memset(dis,,sizeof(dis));
memset(jud,false,sizeof(jud));
memset(cub,,sizeof(cub)); //初始化1的目的就是边界。把那些边界的值都赋值为很大。memset赋值1的话,cub里面的数不是1.
max1=;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
scanf("%d",&cub[i][j]);
dis[i][j]=;
jud[i][j]=true;
}
for(x=;x<=m;x++)
for(y=;y<=n;y++){
ans=;
dfs(x,y);
if(max1<dis[x][y]) max1=dis[x][y];
}
printf("%d\n",max1);
return ;
}