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 谢谢