问题标题: 深度优先搜索

1、深度优先搜索是什么

深度优先搜索是递归的算法，主要是通过递归实现平面类型的题目，特**是【不撞南墙不回头】
如[过河卒](https://www.luogu.com.cn/problem/P1002)、[方格取数](https://www.luogu.com.cn/problem/P1004)之类的问题
2、深度优先搜索的缺点

1、十分复杂,因为递归相对于简要的递归来说，十分复杂，难以操作，一旦出现错误便难以找寻

2、时间复杂度极大，因为是主要对于平面使用且看不到**胡同就不回头，导致要将图上全部走一遍才能找到解，而且极有可能重复，比如一个问题是找n* n的平面，那么时间复杂度为O(n^2)（实际上更高，这只是粗略的计算），因此在未优化前最好不要让n>=1000，后果自负

3、深度优先搜索的优点：

因为适用于二维，因此对于拆数问题与平面路径问题等在只学到算法的情况下只能用深度优先搜索（宽度优先搜索不在算法时学，因为需要队列）

4、未优化情况（即雏形）模板

int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}},sx,sy,fx,fy,cnt,n,m;

void dfs(int x,int y){

if(x==sx && y==sy){
    ++cnt;
    return;
}
for(int i=0;i<4;i++){
    int nx=x+dir[i][0],ny=y+dir[i][1];
    if(nx>0 && ny>0 && nx<=n && ny<=m && !vis[nx][ny]){
        vis[nx][ny]=true;
        dfs(nx,ny);
        vis[nx][ny]=false;
    }
}
}

5、dfs的优化，记忆化搜索

大家都知道，算法大部分都有优化，没错，它也有优化，即记忆化搜索
说白了就是多弄个数组，如果到了这个地步但是数组里有存（即遍历过），则return数组里的，但前提是dfs数组会改为int类型，因此代码会稍稍改变一下，因为变成int类型就代表会被直接输出
我的话讲完了，拜拜