DFS(深度优先搜索)

_cola_ · 2025-01-15 15:58:18 · 个人记录

作为大家第一个学的搜索DFS大家一定很熟悉，什么八皇后，走迷宫……都是大家学DFS时写的，那么就让我给大家回顾一下吧！

1.01DFS模板(俗称爆搜):

// 在此之前要定义一个数组p,用来标记选或不选
void dfs(int step,……){
    // 可以加一点剪枝。
    if(step>n){
      // 题目中的操作。
      return;
    }
    p[step]=1;
    dfs(step+1,……)；
     p[step]=0;
    dfs(step+1,……)；
}

2.二维DFS模板:

F1(不建议大家写):

void dfs(int x,int y){
    if(超过边界或走过或其它条件) return;
    // 标记。
    // 直接手打方向,以下写的是上下左右的dfs。
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x,y+1);
    // 取消标记。
}

F2:

// 以下写的是上下左右的方向数组,最常用于BFS。
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
    if(超过边界或走过或其它条件) return;
    // 标记。
    for(int i=0;i<4;i++){// 枚举所有方向
        int nx=dx[i]+x,ny=dy[i]+y;
        dfs(nx,ny);
    }
    // 取消标记。
}