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