深度优先搜索DFS是非常重要的一个内容深度优先搜索有三个重要的点出口终止条件决定何时结束当前分支状态标记与回溯保证不重复访问并能回溯上一个状态遍历顺序与剪枝决定搜索效率并提前排除无效分支而每个程序由于所求的东西不同出口、状态标记与回溯、遍历顺序与剪枝也都不相同有些程序不需要回溯也有些程序不需要状态标记。下面是基础 DFS 的伪代码框架voiddfs(intd){if(出口){操作;return;}for(循环次数){if(合法的条件){状态标记;dfs(d1);回溯;}}}而 DFS 用的比较多的地方就是跑迷宫下面是一道关于迷宫的例题P1605 迷宫我们可以从起点开始往上、下、左、右四个方向走只要下一个位置不是障碍物就可以走把走过的位置都进行标记标记过的地方不能往回走只要当前位置为终点位置就把答案加一。下面是本题的代码#includebits/stdc.husingnamespacestd;constintmaxn15;intn,m,t,sx,sy,fx,fy,ans,vis[maxn][maxn];intdx[]{-1,0,1,0};intdy[]{0,1,0,-1};charmp[maxn][maxn];voiddfs(intx,inty){if(xfxyfy){ans;return;}for(inti0;i4;i){intxxxdx[i],yyydy[i];if(xx1xxnyy1yym!vis[xx][yy]mp[xx][yy]!#){vis[xx][yy]1;dfs(xx,yy);vis[xx][yy]0;}}}intmain(){cinnmtsxsyfxfy;for(inti1;in;i){for(intj1;jm;j)mp[i][j].;}for(inti1;it;i){intx,y;cinxy;mp[x][y]#;}vis[sx][sy]1;dfs(sx,sy);coutans;return0;}其中dx和dy表示四个方向mp是迷宫的地图。对于其他的 DFS 题目只要找到了出口、状态标记与回溯、遍历顺序与剪枝就可以很轻松的把题目写出来。