为啥这样写第二个点会tle

P1434 [SHOI2002] 滑雪

SigmaQuadrant @ 2018-08-19 22:47:55

改代码改成记忆化搜索最后还是过了,但是不是很清楚原来的代码为啥第二个点会tle,我的思路就是如果四边有比这个高的点,那么就不去搜索这个点,感觉这样做效率并没有很低,希望有大佬来分析一下原因

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int r,c;
int mp[105][105];
int vis[105][105];
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
int res=0;
void dfs(int x,int y,int ans)
{
    res=max(res,ans);
    for(int i=0; i<4; i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&!vis[nx][ny]&&mp[nx][ny]<mp[x][y])
        {
            vis[nx][ny]=1;
            dfs(nx,ny,ans+1);
            vis[nx][ny]=0;
        }
    }
}
int main()
{
    cin>>r>>c;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
            cin>>mp[i][j];
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
        {
            int t=mp[i][j];
            if(mp[i+1][j]>t||mp[i-1][j]>t||mp[i][j+1]>t||mp[i][j-1]>t)
                continue;
            vis[i][j]=1;
            dfs(i,j,1);
            vis[i][j]=0;
        }
    cout<<res<<endl;
    return 0;
}

by 斗神·君莫笑 @ 2018-08-19 23:57:22

那有可能走不动就死了啊


by SigmaQuadrant @ 2018-08-20 10:43:44

@斗神·君莫笑 能再详细一点吗,但是不太懂qwq


|