DFS入门

概念

这是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法。它从起始顶点开始，沿着一条路径尽可能深地探索下去，直到无法继续，然后回溯到前一步，继续探索其他分支。

示例：
假设有一个二叉树，节点结构为包含值、左子节点和右子节点。我们从根节点开始进行深度优先搜索。如果先访问左子树，那么会一直沿着左子树的路径向下访问，直到遇到叶子节点（没有子节点的节点）。例如，对于二叉树节点值依次为 1（根节点）、2（左子节点）、3（右子节点），深度优先搜索先访问 1，然后 2，此时 2 是叶子节点，就回溯到 1，再访问 3。

应用场景

常用于解决图的连通性问题、迷宫求解等。比如在迷宫中，把每个岔路口看作一个节点，通道看作边，使用深度优先搜索可以找到从起点到终点的一条路径。

基本模型

void dfs(int step)
{//特殊情况处理（一般是结束递归的情况）//枚举当前每一种可能for（i=1;i<=n；++i）//在枚举的每一种可能中递归dfs （step+1）；
}

例题

输入一个正整数n，请按照字典序输出1-n
的全排列，每个排列输出一行，每个数字后面跟一个空格。
Sample Input
3
Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include < bits/stdc++.h> 
using namespace std;
int n;
int num[10],vis[10];
void dfs(int step);
int main(
{while(scanf("%d", &n)==1){memset(vis, 0,sizeof(vis));dfs(1);}return 0;
}void dfs(int step) //思考：参数step的含义是？
{if(step == n+1){for(int i = 1; i <= n; i++)printf"%d", num[i):printf("\n");return;}for(int i = 1; i <= n; i++){if(vis[i] == 0){num[step] = i;vis[i] = 1;dfs(step+1);vis[i] = 0;//回溯，难点}}
}

一个迷宫，在规定的第t秒走到出口算胜利，一秒走一步，不可停留，只有上下左右四个方向
Sample Input
445
S.X.
…X.
…XD
Sample Output
3 4 5
S.X.
…X.
…D
000
NO YES

奇偶性剪枝
可以把Map看成这样：
010101
101010
010101
101010
010101
从为0的格子走一步，必然走向为1的格子
从为1的格子走一步，必然走向为0的格子
即：
0->1 或1->0 必然是奇数步
0->0 走1->1 必然是偶数步
结论：
当遇到丛0走向0但是要求时间是奇数的或者
从1走向0但是要求时间是偶数的
都可以直接判断不可达！

#include <bits/stdc++.h>
using namespace std; 
char Map[9][9]; int n,m,t,di,dj;
bool escape;
int dir[4][2]={{0,-13,{0,13,(1,03,(-1,01};
void dfs (int si, int sj,int cnt); 
int main(
{int ij,si, sj;while(cin> >n> >m>>t){if(n==0 && m==0 && t==0)break;int wall=0;for(i=1;i<=n;i++){    for(j=1;j<=m;j++){cin > > Mapli]i];if(Map|i][j]=='S'){ si=i; sj=j; }else if(Map|i][j]=='D'){ di=i; dj=j; }else if(Map[i][j]=='X')wall++;}}if(n*m-wall <=t){cout<<"No"<<endl;continue;}escape=0; Map[si][sj]='X';dfs(si, sj,O);if(escape) cout<<"YES" < <endl;elsecout<<"No"<<endl：}return 0;
}void dfs(int si,int sj,int cnt)
{ int i,temp;if(si>n || sj>m || si<=0 || sj<=0)   return;if(cnt==t && si==di && sj==dj)   escape=1;if(escape)    return;temp=(t-cnt)-abs(si-di)-abs(sj-dj); if(temp<0||temp%2==1)    retern;for(i=0;i <4;i++){ if(Map[si+dir[i][0]][sj+dir[i][1]]!='X'){ Map[si+dir[i][O]][sj+dir[][1]]='x';dfs(si+dir[i][0],sj+dir[i][1],cnt+1);Map[si+dir[i][0]||sj+dir|i][1]]='.;}}return;
}