DFS

参考视频

前置知识：二叉树的遍历

三种遍历

先根遍历（根左右）
中根遍历（左根右）
后根遍历（左右根）

注意：这里的左右为左右子树

e.g.

1. 先根遍历：271653894
1. 中根遍历：175632849
1. 后根遍历：153674982

二叉树的确定

给定先根和中根、中根和后根遍历结果，可以唯一确定二叉树

e.g. 上面，在先根中确定2为根，在中根中找到2，则2前后分别为其左右子树；再在先根中找到7，在中根中找到7，则7前后为其左右子树，以此类推。中根后根与前根后根是对称的。
给定先根和后根遍历结果，不能唯一确定二叉树

只知道根数量而不知道左右子树数量

递归

递归特征：大问题与子问题除了规模其他都一样

斐波那契数列的递归实现

int fi(int a){
    if (a==0||a==1) return 1;
    else return fi(a-1)+fi(a-2);
}

即有一个特定模板：

即先写程序出口（不需要递归的特殊情况），再写普通情况（递归）

全排列问题

输入一个正整数n，按字典序输出n-1的全排列

递归特征

若第一个数确定，剩余的问题就是其余n-1个数的全排列
若前k个数已经排好，剩余问题就是其余n-k个数的全排列

代码实现

#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){  // 前n位都放好了，进行输出
        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){  // 第i位数没用过
            num[step]=i;  // nun中当前这一位保存一个i
            vis[i]=1;  // i被用过了，做标记1
            dfs(step+1); 
            vis[i]=0;
        }
    }
}

若n==3：

vis：0 0 0 0 step==1

进入for循环: vis[1]==0

使num[1]=1 vis[1] = 1

num： 0 1 0 0 0

vis：0 1 0 0 表示1用过了

vis： 0 1 0 0 step==2

进入for循环: vis[2]==0

num[2]=2 vis[2] = 1

num： 0 1 2 0 0

vis：0 1 1 0 表示1,2用过了

vis：0 1 1 0 step==3

进入for循环: vis[3]==0

num[3]=3 vis[3] = 1

num： 0 1 2 3 0

vis：0 1 1 1 表示1,2,3用过了

vis：0 1 1 1 step==4

step == 3+1成立，到达边界，则输出num[1]到num[n] 123

return 到dfs(3)中（谁调用的返回谁）

dfs(3)：vis[3]=0 vis：0 1 1 0 程序结束返回dfs(2)

dfs(2)：vis[2]=0 vis：0 1 0 0

此时进行下一次循环 i==3，vis[3]==0

num[2]=3,vis[3]=1

num： 0 1 3 0

vis：0 1 0 1 表示1,3用过了

再进入dfs(3)，重复上述操作后

num：0 1 3 2

vis：0 1 1 1

进入dfs(4)到达边界输出 132

return 到dfs(3)中重复上述过程

若没有vis[i]=0的回溯，则第一遍return后vis仍保持全标记1状态，则无法再输出其他排列直接结束

基本模型

关键在于着眼于当下如何做，下一步的做法与当前一样，只是参数不同

void dfs(int step){
特殊情况处理(结束递归情况)
枚举当前每一种可能for(int i=1;i<=;i++)
	在枚举的每一种可能中，递归dfs(step+1);
	回溯
}

例：迷宫搜索

Tempter of the Bone

Problem Description

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

‘X’: a block of wall, which the doggie cannot enter; ‘S’: the start point of the doggie; ‘D’: the Door; or ‘.’: an empty block.

The input is terminated with three 0’s. This test case is not to be processed.

Output

For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.

Sample Input
1
2
3
4
5
6
7
8
9
10
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
1
2
NO
YES

分析：

每个block只能走一次
恰好给定时间到达出口
剪枝条件：
- 若可走的block总数小于时间：全走完都开不了门，肯定NO
- 若起点在左上角，门在右下角，没有障碍物且最短路径（曼哈顿距离：行坐标差减列坐标差）都比时间长，肯定NO
- 奇偶性剪枝（应用条件：每个格子只能等一秒）：
  
  使行列坐标相加为偶数的标为0，为奇数的标为1，发现1的下一步一定为0，0的下一步一定为1
  
  那么如果从0走到1或从1走到0，所需时间为奇数；如果从1走到1或从0走到0，所需时间为偶数
  
  那么如果规定时间为偶数，则从0到1或从1到0肯定NO，反之亦然。

代码

#include <iostream>
#include <algorithm>
#include <string>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
char mmap[9][9];  // 存储地图 注意地图要比数据范围大一点
int n,m,t,escape;
int si,sj,di,dj;  // 记录起始与结束点坐标
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};  // 进行上下左右四个方向的行走
void dfs(int x, int y, int cnt){  // 行列坐标，已经花的时间
  if (x>n||y>m||x<=0||y<=0) return ;  // 越过边界，跳过
  if (cnt==t&&x==di&&y==dj) {  // 在开门时间到达出口
    escape=1;  // 标记逃离成功
    }
  if (escape) return ;
  // t-cnt:剩余时间 两abs:剩余距离
  int tmp=((t-cnt)-abs(di-x)-abs(dj-y));
  // 小于零：剩余时间内走不到终点
  /* 是奇数：为了到达门口，剩余时间与剩余距离的奇偶性一定要相同
  奇数-奇数=偶数   偶数-偶数=偶数
  故tmp一定要是偶数才能保证走到门口，否则包走不到
  即奇偶性剪枝
  */
 // 该奇偶性剪枝可以在主函数里写，因为时间和距离是同步进行的
  if (tmp<0) return ;
  // 四个方向遍历
  for (int i = 0 ;i < 4;i++){
    if (mmap[x+dir[i][0]][y+dir[i][1]]!='X'){  // 不是障碍物
      mmap[x+dir[i][0]][y+dir[i][1]]='X';  //修改
      dfs(x+dir[i][0],y+dir[i][1],cnt+1);  //递归
      mmap[x+dir[i][0]][y+dir[i][1]]='.';  //回溯，这样可以回到上一步换一条路走
    }
  }
  return ;
}
int main(){
  while(cin >> n >> m >>t){
    if (n==0&&m==0&&t==0) break;  // 结束条件
    int block = 0;  // 障碍物数量：用来剪枝
    for(int i = 1;i <=n;i++){
      for(int j = 1; j<=m;j++){
        cin >> mmap[i][j];
        if (mmap[i][j]=='S') {
          si=i;
          sj=j;
        }
        else if (mmap[i][j]=='D') {
          di=i;
          dj=j;
        }
        else if (mmap[i][j]=='X') block++;
      }
    }
    // 剪枝1：迷宫格子数量减去障碍物数量小于等于开门时间，一定出不去
    if (n*m-block<=t) {
      cout << "NO"<<endl;
      continue;
    }
    // 剪枝2：见dfs里的解释
    if ((t-(abs(di-si)+abs(dj-sj)))%2==1){
      cout << "NO"<<endl;
      continue;
    }
    // escape标记是否成功，把起点标为障碍物，确保不会再回来
    escape = 0, mmap[si][sj]='X';
    dfs(si,sj,0);
    // 判断是否能逃离
    if (escape) cout <<"YES" <<endl;
    else cout << "NO" << endl;
  }
  return 0;

}

红魔咖啡馆

【算法】DFS

DFS