蒟蒻求助!!TLE#2!

P1434 [SHOI2002] 滑雪

BearBig @ 2022-06-21 20:34:41

闰土

#include<bits/stdc++.h>
using namespace std;
int mp[105][105];int n,m;
bool vis[105][105];int tot(-2147483647);
bool inrange(int x,int y)
{return 1<=x and x<=n and 1<=y and y<=m;}
void dfs(int i,int j,int presum)
{
    tot=max(tot,presum);
    if(inrange(i-1,j) and mp[i-1][j]<mp[i][j] and vis[i-1][j]==false)
        {vis[i-1][j]=true;dfs(i-1,j,presum+1);vis[i-1][j]=false;}
    if(inrange(i,j+1) and mp[i][j+1]<mp[i][j] and vis[i][j+1]==false)
        {vis[i][j+1]=true;dfs(i,j+1,presum+1);vis[i][j+1]=false;}
    if(inrange(i+1,j) and mp[i+1][j]<mp[i][j] and vis[i+1][j]==false)
        {vis[i+1][j]=true;dfs(i+1,j,presum+1);vis[i+1][j]=false;}
    if(inrange(i,j-1) and mp[i][j-1]<mp[i][j] and vis[i][j-1]==false)
        {vis[i][j-1]=true;dfs(i,j-1,presum+1);vis[i][j-1]=false;}
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>mp[i][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            dfs(i,j,1);
    cout<<tot;
}

有哪位巨佬帮忙看一看?


by Oranges1234567 @ 2022-06-21 20:45:52

@HeavenGalaxy 需要用记忆化搜索,不然会超时


by Oranges1234567 @ 2022-06-21 20:47:41

@HeavenGalaxy 而且不需要用vis数组,因为一定从高海拔的点到低海拔的点,不会成环


by BearBig @ 2022-06-26 10:03:24

@Oranges1234567 那为什么只有#2超时,难不成其他数据太水。

关键是蒟蒻的学校只讲过DFS BFS啊,记忆化搜索听都没听说过


by Oranges1234567 @ 2022-06-26 22:32:38

@HeavenGalaxy 应该是数据太水,你可以看看题解的记忆化搜索怎么写的


by Hsl123456 @ 2022-07-11 22:04:52

所以#2是啥


by x383494 @ 2022-12-24 22:00:25

@Hsl123456 第二个测试点


by Hsl123456 @ 2022-12-30 20:06:32

@x383494 谢谢


|