C++,第二个点TLE,已经记忆化搜索了,求大神改进

P1434 [SHOI2002] 滑雪

啊偶—0 @ 2017-07-08 12:47:19

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<stack>
using namespace std;
int x,y;
int a[105][105];
int b[105][105];
int ans;
void dfs(int x1,int y1,int step)
{
    if(x1<=0||x1>x||y1<=0||y1>y)return;
    if(b[x1][y1]>=step)return;
    ans=max(ans,step);
    b[x1][y1]=step;
    if(a[x1-1][y1]<a[x1][y1])dfs(x1-1,y1,step+1);//b[x1][y1]=max(b[x1][y1],b[x1-1][y1]-1);}
    if(a[x1+1][y1]<a[x1][y1])dfs(x1+1,y1,step+1);//b[x1][y1]=max(b[x1][y1],b[x1+1][y1]-1);}
    if(a[x1][y1-1]<a[x1][y1])dfs(x1,y1-1,step+1);//b[x1][y1]=max(b[x1][y1],b[x1][y1-1]-1);}
    if(a[x1][y1+1]<a[x1][y1])dfs(x1,y1+1,step+1);//b[x1][y1]=max(b[x1][y1],b[x1][y1+1]-1);}
}
int main()
{
    cin>>x>>y;
    for(int i=1;i<=x;i++)
    for(int j=1;j<=y;j++)
        scanf("%d",&a[i][j]);
    for(int i=1;i<=x;i++)
    for(int j=1;j<=y;j++)
        dfs(i,j,1);//我尝试在这个地方加上判断(i,j)为附近最高点,但是会错,求告知;
    cout<<ans;
    return 0;
}
望各位大神能为在下指点一二,不胜荣幸(感觉好二啊。。。

by zjp_shadow @ 2017-07-08 13:32:20

您可以将所有点的高度进行排序 从高到低一个个进行搜索 正确度应该可以保证(因为我自己就这样弄的23333)


|