我对dfs的理解:对每一个数据进行遍历,直到越界或者得到正确结果
通常对于一些路线问题
类型1:迷宫矩阵图类
eg1:滑雪
题目大意:让你找出从一个区域内的最长下降序列(坡度依次递减),你可以上下左右移动
思路:用深度搜素要做的就是一个个数据去搜索,因此这个过程要用到递归,也要想到终止条件是什么(递归边界),最后我们还要求取最大值
//int dx[4]={0,0,1,-1};
//int dy[4]={1,-1,0,0};//作为全局变量
int dfs(int x,int y){
if(s[x][y])return s[x][y];//记忆化搜索
s[x][y]=1;//题目中答案是有包含这个点的
for(int i=0;i<4;i++)
{ int xx=dx[i]+x;
int yy=dy[i]+y;//四个方向
if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
dfs(xx,yy);
s[x][y]=max(s[x][y],s[xx][yy]+1);
}
}
return s[x][y];
}