caojiaming @ 2023-05-09 21:13:22
#include <bits/stdc++.h>
using namespace std;
int n,m,h[110][110];
int ans=-1;
void dfs(int x,int y,int cnt,int lst)
{
if(x>n||x<1||y>m||y<1)
{
return;
}
if(h[x][y]>=lst) return;
ans=max(ans,cnt);
lst=h[x][y];
dfs(x+1,y,cnt+1,lst);
dfs(x-1,y,cnt+1,lst);
dfs(x,y+1,cnt+1,lst);
dfs(x,y-1,cnt+1,lst);
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&h[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dfs(i,j,1,1e9);
}
}
cout<<ans<<endl;
return 0;
}
这是O(n²m²)复杂度对吧
n<=100,m<=100,
不正是10⁸吗?
那为什么还是TLE
(注:dfs遍历,只会把每个格子遍历一次,所以复杂度为nm)
by yzm0325 @ 2023-05-09 21:15:45
10^8就是Tle啊
by caojiaming @ 2023-05-09 21:17:00
@Zhuyiming0325
10^8就是计算机的速度,1s正好过
by yzm0325 @ 2023-05-09 21:20:34
@caojiaming 这个也很悬谁能说准那记搜(?
我太弱可能说不准
by yzm0325 @ 2023-05-09 21:21:43
到每个点的时候记录一下,再到这里时直接用这个结果(?
by zjw806903 @ 2023-05-26 19:12:16
也许你可以考虑用dp?
by naixvjiang @ 2023-05-27 11:01:00
考虑下记忆化或者回溯?
by fuck__luogu @ 2023-07-04 10:55:36
@caojiaming 谢谢你