报名明年4月蓝桥杯软件赛的同学们，如果你是大一零基础，目前懵懂中，不知该怎么办，可以看看本博客系列：备赛20周合集
20周的完整安排请点击：20周计划
每周发1个博客，共20周。
在QQ群上答疑：
文章目录
- 1. 搜索概述
- 2. DFS概述
-
- 2.1 DFS的代码框架
- 3. DFS与排列
-
- 3.1 输出全排列
- 3.2 输出部分排列
- 4. DFS与组合
- 5. DFS与连通性
- 6. DFS例题
-
- N皇后
- 与或异或
- 有奖问答
- 飞机降落
- 最大数字
- 买瓜
- 7. 习题
第12周: DFS
如果问蓝桥杯一定会考什么，绝对不会缺席的那种，答案肯定是：DFS！
例如2023年蓝桥杯省赛，有8道题和DFS有关，或者直接用DFS，或者基于DFS的高级算法：有奖问答、分糖果、飞机降落、与或异或、树上选点、异或和、景区导游、像素放置。
1. 搜索概述
有人说，只要学通了搜索，在蓝桥杯省赛上就能稳得二等奖。这个说法有开玩笑的意思，其实他的重点是强调搜索的重要性。
为什么搜索这么重要？因为搜索是“暴力法”的具体实现，暴力法是最直接、最充分利用计算机强大算力的方法。竞赛题目很多可以用暴力法做，即使暴力法的效率不高，在蓝桥杯这样的赛制中，也可能通过部分测试，得到一些分数。
什么是暴力法？一道算法题，给定输入，有对应的输出。自然地会有一种最简单的解题方法：把所有可能的情况都罗列出来，然后逐一检查，根据给定的输入找到对应的输出，从而得到答案。这种方法称为暴力法（Brute force）。
虽然所有问题都能用暴力法来求解，但暴力法也往往是“低效”的代名词。暴力法虽然低效，但优点是简单，相对其他“高效”算法，暴力法的代码一般都更短、更好写。在蓝桥杯大赛中，当拿到一个题目后，如果没有更好的思路，可以考虑用暴力法，通过一部分测试，拿到部分分数，这是蓝桥杯大赛的必备技能。
暴力法的主要手段之一是搜索。很多情况下，如果不会写搜索的代码，那么连暴力法都实现不了。这是为什么搜索如此重要的原因。
搜索包括两种基本技术：宽度优先搜索（BFS，Breadth-First Search）、深度优先搜索（DFS，Depth-First Search）。它们是算法竞赛常见的知识点，DFS尤其常见，是蓝桥杯考核最多的知识点。
下面以老鼠走迷宫为例说明BFS和DFS的原理。
给定一个迷宫，迷宫内道路错综复杂，老鼠从入口进去后，如何找到出口？由于老鼠对迷宫一无所知，它只能暴力地搜索所有可能的道路，直到找到一个出口。
有两种走迷宫方案，它们分别体现了BFS和DFS的原理。
（1）一只老鼠走迷宫。它在每个路口，都选择先走右边（或者都选择先走左边），能走多远就走多远；直到碰壁无法再继续往前走，然后往回退一步，这一次走左边，然后继续往下走。用这个办法，只要没遇到出口，就会走遍所有的路，而且不会重复，这里规定回退不算重复走（即使算重复走，也只多走一次）。这个方法就是DFS，概况DFS的思路：一路到底、逐步回退。
（2）一群老鼠走迷宫。假设老鼠无限多，这群老鼠进去后，在每个路口，都派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有别的老鼠探索过了，也停下。很显然，在遇到出口前，所有的道路都会走到，而且不会重复。这个方法就是BFS，概况BFS的思路：全面扩散，逐层递进。
BFS和DFS的计算量是多少？对迷宫问题来说，计算量体现在它们在迷宫内部走了多少路口和边。显然不管是BFS和DFS，每个路口和边，它们都只走一次。设路口有n个，边有m条，计算量是O(n+m)。概括地说，BFS和DFS都能找到出口，且都需要暴力搜到所有的路口和道路，它们的计算量是一样的。
DFS的优势：DFS能搜索并输出从入口到出口的所有路径，BFS不行。从入口到出口的路径数量极多，例如一个十几个路口，几十条边的迷宫，路径可能多达数万。一般不会要求输出路径，或输出路径的数量。
BFS的优势：BFS能快速找到最短路径，DFS很困难。为什么BFS能快速找到最短路径？以某个路口为例，当有老鼠第一次到达这个路口时，这只老鼠走过的路径一定是最短路径。因为如果是兜圈子过来的，这只老鼠就不是第一个到了。BFS搜最短路径，计算量是O(n+m)的。在算法竞赛中，用BFS求最短路径是常见考点。如果用DFS求最短路径，只能先搜出所有路径，再比较得到最短的。由于路径数量极多，所以计算量极大。
编码时，BFS需要用队列这种数据结构来实现，“BFS = 队列”；DFS用递归实现，“DFS = 递归”。DFS的编码比BFS的编码简单一些。
2. DFS概述
DFS是算法竞赛的必考知识点，在任何一场算法竞赛中都不会缺席。
（1）知识点：DFS是必学的基础算法，是暴力技术的体现。
（2）编码：DFS的编码很有技巧性，能很好地考验编码能力。
（3）扩展：DFS是很多高级算法的基础。
（4）应用：DFS的应用很广，题目可难可易。
2023年的蓝桥杯省赛，有三道纯DFS题（有奖问答、与或异或、分糖果，仅仅只用到DFS，没有用到其他知识点）是作为填空题出现的，一题仅有5分。这说明出题人认为DFS是必须掌握的基础知识点，一道纯DFS题只能给5分。这一年还有多道大题用到DFS，但是需要结合其他算法。
2.1 DFS的代码框架
下面给出DFS的代码框架，DFS用递归实现。
ans; //答案，常常用全局变量表示
void dfs(层数，其他参数){
if (到达目的地、或者出局){ //到达最底层，或者满足条件退出
更新答案ans; //答案一般用全局变量表示，ans是最优解
return; //递归返回，即返回到上一层
}
(剪枝) //在进一步DFS之前剪枝
for (用i遍历下一层所有可能的情况) //对每一个情况继续DFS
if (used[i] == 0) { //如果状态i没有处理过，就可以进入下一层dfs
used[i] = 1; //标记状态i为已经使用，在后续dfs时不能再使用
dfs(层数+1，其他参数); //下一层，即搜小规模后继续dfs
used[i] = 0; //恢复状态i，回溯时，不影响上一层对这个状态的使用
}
return; //返回到上一层
}
代码看起来不长，但是对初学者来说还是有学习难度。在DFS框架中，最让初学者费解的是第10行和第12行，它们是对递归的理解。
第10行的used[i] = 1，称为“保存现场”，或“占有现场”。
第12行的used[i] = 0，称为“恢复现场”，或“释放现场”。
请读者在大量编码的基础上，再回头体会这个框架的作用。
DFS常见的应用场景有：排列组合、连通性。
3. DFS与排列
3.1 输出全排列
本节从DFS的一个基础应用开始：生成排列。排列问题在蓝桥杯题目中常常出现。
全排列问题是典型的“暴力”问题，n个数的全排列，共有n!种，在每个排列中，每个数出现一次，而且只出现一次。
例题 全排列问题
如果n比较小，可以写n个for循环输出全排列。但是这种简单方法只能用于较小的n，如果n比较大，这种方法的代码非常冗长、难看。
DFS非常适合实现全排列，代码清晰、简洁、优美。下面的C++代码能从小到大打印排列。
#include<bits/stdc++.h>
using namespace std;
int n;
int vis[10]; // 访问标记
int a[10]; //需要做全排列的数组
int b[10]; //当前DFS得到的全排列
void dfs(int step) {
if (step == n+1) { //已经对n个数做了全排列，输出全排列
for (int i=1; i<=n; i++)
printf("%5d",b[i]);
printf("\n");
return; //结束，不再继续DFS
}
for (int i = 1; i <= n; i++) { //遍历每个a[i]，放进全排列中
if (vis[i] == 0) { // 数字a[i]不在前面得到的排列中
b[step] = a[i]; // 把a[i]放进排列
vis[i] = 1; // 保存现场：a[i]不能在后面继续用
dfs(step+1); // 继续把后面的数放进排列
vis[i] = 0; // 恢复现场：a[i]重新可以使用
}
}
return;
}
int main() {
cin >> n;
for (int i=1; i<=n; i++) a[i]=i; //赋值得到n个数
dfs(1); //对a[1]~a[n]做全排列
return 0;
}
代码用b[1]~b[n]记录一个全排列。下面以n=3为例，图解代码的执行过程。圆圈内的数字是全排列的数字，例如最上面一行生成的排列是{1, 2, 3}。一共生成6个全排列。用下面的图解释DFS生成全排列的过程。
代码第27行从dfs(1)开始，这是第一次进入dfs()。图中相关的是标注A的位置。第14行进入for循环，在第16行赋值：i=1时b[1]=1；i=2时b[1]=2；i=3时b[1]=3。对应图中最左边三条线上标注的i=1、i=2、i=3。
i=1时，在17行vis[1]=1，表示a[1]=1已经放在排列中，后续不能再用。然后进入dfs(2)，这是第二次进入dfs()。图中相关的是标注B的位置。
dfs(2)时，第14行进入for循环。当i=1时，第15行判断vis[1]已经被使用，所以不再继续，用图中最上面的虚线表示i=1不再继续。i=2和i=3可以继续往后执行，例如i=2时，先赋值b[2]=2；然后进入dfs(3)，并赋值b[3]=3；最后进入dfs(4)，在第8行判断已经得到全排列，输出第一个全排列{1, 2, 3}。图中相关的是标注C的位置。
后续过程，读者可以继续模拟。特别注意第17行vis[i]=1和第19行vis[i]=0的作用。
Java代码。
import java.util.Scanner;
public class Main {
static int n;
static boolean[] vis;
static int[] a;
static int[] b;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
vis = new boolean[10];
a = new int[10];
b = new int[10];
for (int i = 1; i <= n; i++) a[i] = i;
dfs(1);
}
static void dfs(int step) {
if (step == n + 1) {
for (int i = 1; i <= n; i++)
System.out.printf("%5d", b[i]);
System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == false) {
b[step] = a[i];
vis[i] = true;
dfs(step + 1);
vis[i] = false;
}
}
}
}
Python代码。
n = int(input())
vis = [0] * 10
a = [0] * 10
b = [0] * 10
def dfs(step):
if step == n + 1:
for i in range(1, n+1):
print("%5d" %b[i], end="")
print()
return
for i in range(1, n+1):
if vis[i] == 0:
b[step] = a[i]
vis[i] = 1
dfs(step + 1)
vis[i] = 0
for i in range(1, n+1): a[i] = i
dfs(1)
3.2 输出部分排列
上述代码是打印n个数的全排列，如果需要打印n个数中任意m个数的排列，略作修改即可。例如n=4，m=3，修改C++代码这两处：第8行把step=n+1改为step=m+1，第9行i<=n改为i<=m。
4. DFS与组合
如果要打印n个数中m个数的组合，同样可以用DFS。
DFS时，选或不选第k个数，就实现了各种组合。下面举两个例子。
（1）输出二进制。以打印000 ~ 111为例，下面是Python代码，C++和Java略。
vis = [0]*10
def dfs(k): #深搜到第k个数
if k == 4: #已经得到3个数的组合
for i in range (1,4): print(vis[i],end='')
print(' ',end='')
else:
vis[k] = 0 #第k个选数字0，或者理解为第k个不选(0表示不选)
dfs(k + 1) #继续搜下一个
vis[k] = 1 #第k个选数字1，或者理解为第k个选中(1表示选中)
dfs(k + 1) #继续搜下一个
dfs(1)
输出：000 001 010 011 100 101 110 111
如果要反过来，只需要交换7、9行，输出：111 110 101 100 011 010 001 000
（2）输出组合。以包含3个元素的集合{a, b,c}为例，输出它所有的子集。
下面是Python代码，C++和Java略。代码输出： c b bc a ac ab abc
a = [' ', 'a', 'b', 'c']
vis = [0] * 10
def dfs(k):
if k == 4:
for i in range(1, 4):
if vis[i]: print(a[i], end='')
print(' ', end='')
else:
vis[k] = 0 #不选中第k个元素
dfs(k + 1) #继续搜下一个元素
vis[k] = 1 #选第k个元素
dfs(k + 1) #继续搜下一个元素
dfs(1)
5. DFS与连通性
连通性判断是DFS最常见的应用。连通性判断是图论中的一个简单问题，给定一张图，图由点和边组成，要求找到互相连通的部分。连通性判断有三种实现方法：BFS、DFS、并查集，用DFS最简单方便。
在竞赛题中，图常常用方格图给出，每个方格可以向上下左右四个方向走。
DFS判断连通性，步骤如下：
（1）从任意一个点u开始遍历，标记u已经搜过。一般从第一个点开始。
（2）DFS搜索u的所有符合连通条件的邻居点。已经搜过的点标记为已经搜过，后面不用再搜。扩展u的邻居点时，应该判断这个邻居点是不是在边界内。
（3）DFS结束，找到了与u连通的所有点，这是一个连通块。
（4）不与u连通的、其他没有访问到的点，继续用上述步骤处理，找到所有的连通块。
DFS搜连通的计算复杂度如何？因为每个点只用搜一次且必须至少搜一次，共N个点，DFS的复杂度是O(N)的，不可能更好了。
例题 最大连通
C++代码。
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //四个方向
char g[100][100];
int n = 30, m = 60;
int dfs(int x, int y){ //当前位于坐标[x,y]
if (g[x][y] == '0') return 0;
g[x][y] = '0'; //把这个点从1改为0，后面不再搜它
int ans = 1; //统计这个连通块的大小
for (int i = 0; i < 4; i++ ) { //遍历它的4个邻接
int nx = x + dx[i], ny = y + dy[i]; //一个邻居的坐标
if (nx<0 || ny<0 || nx>=n || ny>=m) continue; //这个邻居是否在边界内
ans += dfs(nx, ny);
}
return ans;
}
int main(){
for (int i = 0; i < n; i++ ) cin >> g[i];
int ans = 0;
for (int i = 0; i < n; i++ )
for (int j = 0; j < m; j++ )
if (g[i][j] == '1')
ans = max(ans, dfs(i, j));
cout << ans;
return 0;
}
java代码
import java.util.Scanner;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static char[][] g;
static int n = 30, m = 60;
static int dfs(int x, int y) {
if (g[x][y] == '0') return 0;
g[x][y] = '0';
int cnt = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
cnt += dfs(nx, ny);
}
return cnt;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
g = new char[n][m];
for (int i = 0; i < n; i++) g[i] = scanner.nextLine().toCharArray();
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '1')
ans = Math.max(ans, dfs(i, j));
System.out.println(ans);
}
}
python代码
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n,m = 30,60
def dfs(x, y):
if g[x][y] == '0': return 0
g[x][y] = '0'
cnt = 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m: continue
cnt += dfs(nx, ny)
return cnt
g = list()
for i in range(30): g.append(list(input().strip()))
ans = 0
for i in range(n):
for j in range(m):
if g[i][j] == '1':
ans = max(ans, dfs(i, j))
print(ans)
例题 全球变暖
这是典型的连通性问题，计算步骤是：遍历一个连通块（找到这个连通块中所有的’#‘，并标记已经搜过，不用再搜）；再遍历下一个连通块……；遍历完所有连通块，统计有多少个连通块。
什么岛屿不会被完全淹没？若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。用DFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。
C++代码。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N]; //地图
int vis[N][N]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
vis[x][y] = 1; //标记这个'#'被搜过。注意为什么放在这里
if( mp[x][y+1]=='#' && mp[x][y-1]=='#' &&
mp[x+1][y]=='#' && mp[x-1][y]=='#' )
flag = 1; //上下左右都是陆地，这是一个高地，不会淹没
for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
int nx = x + d[i][0], ny = y + d[i][1];
if(vis[nx][ny]==0 && mp[nx][ny]=='#') //注意为什么要判断vis[][]
dfs(nx,ny); //继续DFS未搜过的陆地，目的是标记它们
}
}
int main(){
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0 ;
for(int i = 0; i < n; i++) //DFS所有像素点
for(int j = 0; j < n; j++)
if(mp[i][j]=='#' && vis[i][j]==0){
flag = 0; //假设这个岛被淹
dfs(i,j); //找这个岛中有没有高地，如果有,置flag=1
if(flag == 0) ans++; //这个岛确实被淹了，统计被淹没岛的数量
}
cout<<ans<<endl;
return 0;
}
Java代码
import java.util.Scanner;
public class Main {
static char[][] mp;
static int[][] vis;
static int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static int flag;
static void dfs(int x, int y) {
vis[x][y] = 1;
if (mp[x][y + 1]=='#' && mp[x][y-1]=='#' && mp[x+1][y]=='#' && mp[x-1][y]=='#')
flag = 1;
for (int i = 0; i < 4; i++) {
int nx = x + d[i][0], ny = y + d[i][1];
if (nx>=0 && ny>=0 && nx<mp.length && ny<mp[0].length && vis[nx][ny]==0 && mp[nx][ny] == '#')
dfs(nx, ny);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
mp = new char[n][n];
vis = new int[n][n];
for (int i = 0; i < n; i++) mp[i] = scanner.next().toCharArray();
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mp[i][j] == '#' && vis[i][j] == 0) {
flag = 0;
dfs(i, j);
if (flag == 0) ans++;
}
System.out.println(ans);
}
}
Python代码。需要在第2行用setrecursionlimit()设置递归深度，否则不能通过100%的测试。
import sys
sys.setrecursionlimit(60000) #设置递归深度
def dfs(x,y):
d = [(0,1),(0,-1),(1,0),(-1,0)]
global flag
global vis
global mp
vis[x][y] = 1
if mp[x][y+1]=='#' and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':
flag = 1
for i in range(4):
nx = x+d[i][0]
ny = y+d[i][1]
if vis[nx][ny]==0 and mp[nx][ny]=='#': dfs(nx,ny)
n = int(input())
mp =[]
for i in range(n): mp.append(list(input()))
vis = []
for i in range(n): vis.append([0]*n)
ans = 0
for i in range(n):
for j in range(n):
if vis[i][j]==0 and mp[i][j]=='#':
flag = 0
dfs(i,j)
if flag == 0: ans+=1
print(ans)
6. DFS例题
N皇后
链接 N皇后
n皇后问题是DFS的经典应用。把n个皇后放在棋盘上，要求不同列、不同行、不在同一条对角线。只能用暴力法尝试所有可能的方案，去掉非法方案，得到合法方案。这实际是排列问题，用DFS搜索所有排列最方便。
题目还要求输出3种方案，而且是字典序的前3种方案。这不难实现，只要按行从1到n、列从1到n的顺序尝试放皇后的方案即可。得到的合法方案，就是字典序的。
本题的主要技巧是如何判断同行、同列、同对角线上是否已经有其他皇后。
设当前处理到第x行，前1 ~ x-1行已经放好了皇后。由于一行只放一个皇后，所以两个皇后同行的冲突情况不用再判断，只需要判断同列、同对角线的情况，对角线又分为主对角线、副对角线。下图中三根虚线，vis是同列，vis1是主对角线，vis2是副对角线。
同列vis上的点有什么特征？它们的y坐标相同。用数组vis[]表示列，vis[y]=1表示第y列已经放了皇后。
主对角线vis1上的点有什么特征？观察上图，沿着主对角线vis1走一步，x坐标加1，y坐标减一，那么x+y不变。也就是说，一条vis1线上的所有点的x+y都相等。例如一条主对角线上的点[1, 5]、[2, 4]、[3, 3]、[4, 2]、[5,1]，都有x+y=6。用数组vis1[]表示主对角线，vis1[x+y]=1表示坐标[x, y]所在的主对角线上已经有皇后。
副对角线vis2上的点有什么特征？沿着副对角线vis2走一步，x和y坐标都加1，那么x-y不变。例如一条副对角线上的点[1, 3]、[2, 4]、[3, 5]、[4, 6]，都有x-y=-2。用数组vis2[]表示副对角线，vis2[x-y+n]=1表示坐标[x, y]所在的副对角线上已经有皇后。这里不能直接用x-y，因为它可能为负数，加上n后就变成了正数。n也可以改为一个大于n的数k，只要保证x-y+k>0就行，不过要记得把vis2[]开大一些，防止溢出。
除了以上技巧，代码的其他部分就是常见的DFS求排列。
C++代码。
#include<bits/stdc++.h>
using namespace std;
int n,tot; //n: 行数; tot:方案数
int ans[20]; //ans[x]: 第x行皇后放在第几列
int vis[30]; //vis[y]=1: 第y列放了皇后
int vis1[30]; //vis1[x+y]=1: 主对角线放了皇后
int vis2[30]; //vis2[x-y+n]=1: 副对角线放了皇后
void dfs(int x){ //第x行，枚举所有列
if(x == n+1) { //已经放完n行
tot++;
if(tot <= 3){
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
cout<<endl;
}
return ;
}
for(int y = 1; y <= n; y++){ //枚举第x行的坐标(x, y)
if(vis[y]) continue; //第y列已经有皇后
if(vis1[x+y]) continue; //主对角线已经有皇后
if(vis2[x-y+n]) continue; //副对角线已经有皇后
ans[x] = y;
vis[y] = 1; vis1[x+y] = 1; vis2[x-y+n] = 1; //保存现场
dfs(x + 1); //继续下一行
vis[y] = 0; vis1[x+y] = 0; vis2[x-y+n] = 0; //恢复现场
}
}
int main(){
cin >> n;
dfs(1);
cout<<tot<<endl;
return 0;
}
java
import java.util.Scanner;
public class Main {
static int n, tot; //n: 行数; tot:方案数
static int[] ans; //ans[x]: 第x行皇后放在第几列
static int[] vis; //vis[y]=1: 第y列放了皇后
static int[] vis1; //vis1[x+y]=1: 主对角线放了皇后
static int[] vis2; //vis2[x-y+n]=1: 副对角线放了皇后
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
ans = new int[n + 1];
vis = new int[n + 1];
vis1 = new int[2 * n + 1];
vis2 = new int[2 * n + 1];
dfs(1);
System.out.println(tot);
}
static void dfs(int x) { //第x行，枚举所有列
if (x == n + 1) { //已经放完n行
tot++;
if (tot <= 3) {
for (int i = 1; i <= n; i++) System.out.print(ans[i] + " ");
System.out.println();
}
return;
}
for (int y = 1; y <= n; y++) { //枚举坐标(x, y)
if (vis[y] == 1) continue; //第y列已经有皇后
if (vis1[x+y] == 1) continue; //主对角线已经有皇后
if (vis2[x-y+n] == 1) continue; //副对角线已经有皇后
ans[x] = y;
vis[y] = 1; vis1[x+y] = 1; vis2[x-y+n] = 1; //保存现场
dfs(x + 1); //继续下一行
vis[y] = 0; vis1[x+y] = 0; vis2[x-y+n] = 0; //恢复现场
}
}
}
python
#pypy
n = int(input())
tot = 0 # tot:方案数
ans = [0] * 20 # ans[x]: 第x行皇后放在第几列
vis = [0] * 30 # vis[y]=1: 第y列放了皇后
vis1 = [0] * 30 # vis1[x+y]=1: 主对角线放了皇后
vis2 = [0] * 30 # vis2[x-y+n]=1: 副对角线放了皇后
def dfs(x):
global tot
if x == n+1: # 已经放完n行
tot += 1
if tot <= 3:
for i in range(1, n+1): print(ans[i], end=' ')
print()
return
for y in range(1, n+1): # 枚举第x行的坐标(x, y)
if vis[y] or vis1[x+y] or vis2[x-y+n]: continue
ans[x] = y
vis[y], vis1[x+y], vis2[x-y+n] = 1,1,1 # 保存现场
dfs(x + 1) # 继续下一行
vis[y], vis1[x+y], vis2[x-y+n] = 0,0,0 # 恢复现场
dfs(1)
print(tot)
与或异或
链接 与或异或
题目的思路很简单。10个逻辑门，每个逻辑门有与、或、异或三种选项，在这10个逻辑门的所有排列中（共种），问有多少种排列的最后计算结果是1。
这一题是DFS求组合的简单应用。读者可以与前面DFS求组合的基本应用比较。
下面是C++代码。代码的计算量有多少？dfs()在第27行中继续做3次dfs()，一共有10个逻辑门，所以一共做了次dfs。每次dfs在check()中做两重for循环约十几次。所以总计算量很小。
C++代码
#include<bits/stdc++.h>
using namespace std;
int a[5][5]={{1,0,1,0,1}}; //记录图中圆圈内的值，并初始化第1行
int gate[11]; //记录10个逻辑门的一种排列
int ans; //答案
int logic(int x, int y, int op){ //逻辑操作：c=1:与; c=2:或; c=3:异或
if(op == 1) return x & y; //与
if(op == 2) return x | y; //或
return x ^ y; //异或
}
int check(){ //检查10个逻辑门的排列，最后out是否为1
int op = 0;
for(int i = 1; i <= 4; i++) //从上到下有4行逻辑门
for(int j = 0; j <= 4 - i; j++) //每一行从左到右
a[i][j] = logic(a[i-1][j], a[i-1][j+1], gate[op++]);
if(a[4][0]) return 1; //out=1，结果正确
return 0;
}
void dfs(int k){ //第k个逻辑门
if(k == 10){ //一共有10个逻辑门，现在都分配好了。下面模拟这一种组合方式
if(check()) ans++; //out=1，结果正确
return;
}
for(int i = 1; i <= 3; i++){ //第k个逻辑门有三种选择：与、或、异或
gate[k] = i; //记录第k个逻辑门：与、或、异或
dfs(k + 1); //继续深搜第k+1个逻辑门
}
}
int main(){
dfs(0);
cout<<ans;
return 0;
}
读者可能注意到，在dfs()中并没有做DFS常见的“保存现场、恢复现场”操作。因为10个逻辑门是相互独立的，每个逻辑门独立选“与、或、异或”，与其他逻辑门无关。而前面介绍的数字的全排列，一个数字被使用后，就不能放到其他位置，所以需要用“保存现场”占住它。
java代码
public class Main {
static int[][] a = new int[5][5]; //记录图中圆圈中的值
static int[] gate = new int[11]; //记录10个逻辑门的一种排列
static int ans; //答案
static int logic(int x, int y, int op) { //逻辑操作：c=1:与; c=2:或; c=3:异或
if(op == 1) return x & y; //与
if(op == 2) return x | y; //或
return x ^ y; //异或
}
static int check() { //检查10个逻辑门的排列，最后out是否为1
int op = 0;
a[0][0] = 1; a[0][1] = 0; a[0][2] = 1; a[0][3] = 0; a[0][4] = 1;
for(int i = 1; i <= 4; i++) //从上到下有4行逻辑门
for(int j = 0; j <= 4 - i; j++) //每一行从左到右
a[i][j] = logic(a[i-1][j], a[i-1][j+1], gate[op++]);
if(a[4][0] == 1) return 1; //out=1，结果正确
return 0;
}
static void dfs(int k) { //第k个逻辑门
if(k == 10) { //10个逻辑门都分配好了。下面模拟这一种组合方式
if(check() == 1) ans++; //out=1，结果正确
return;
}
for(int i = 1; i <= 3; i++) { //第k个逻辑门有三种选择：与、或、异或
gate[k] = i; //记录第k个逻辑门：与、或、异或
dfs(k + 1); //继续深搜第k+1个逻辑门
}
}
public static void main(String[] args) {
dfs(0);
System.out.println(ans);
}
}
python代码
a = [[0 for _ in range(5)] for _ in range(5)] #记录图中圆圈中的值
gate = [0] * 11 #记录10个逻辑门的一种排列
ans = 0 #答案
def logic(x, y, op): #逻辑操作：c=1:与; c=2:或; c=3:异或
if op == 1: return x & y #与
if op == 2: return x | y #或
return x ^ y #异或
def check(): #检查10个逻辑门，最后out是否为1
op = 0
a[0] = [1, 0, 1, 0, 1]
for i in range(1, 5): #从上到下有4行逻辑门
for j in range(0, 5 - i): #每一行从左到右
a[i][j] = logic(a[i-1][j], a[i-1][j+1], gate[op])
op += 1
if a[4][0] == 1: return 1 #out=1，结果正确
return 0
def dfs(k): #第k个逻辑门
global ans
if k == 10: #一共有10个逻辑门，现在都分配好了。下面模拟这一种组合方式
if check() == 1: ans += 1 #out=1，结果正确
return
for i in range(1, 4): #第k个逻辑门有三种选择：与、或、异或
gate[k] = i #记录第k个逻辑门：与、或、异或
dfs(k + 1) #继续深搜第k+1个逻辑门
dfs(0)
print(ans)
有奖问答
链接 有奖问答
这一题是C++组的填空题，填空题对运行时间要求不高，可以用比较耗时的算法做。
本题的正解是动态规划DP，计算量小，运行时间快。不过因为是填空题，可以用暴力方法做，即用DFS编码直接搜索所有情况。虽然DFS的计算量比DP大很多，但是思路简单，编码时间短。
下面是C++代码。dfs()模拟做题过程，思路直接。
C++
#include<bits/stdc++.h>
using namespace std;
int ans=0;
void dfs(int x,int score,int k){ //x:第x题; score:得分; k:对错
if(k==0) score=0; //答错了，归零
else{
score+=10; //答对了
if(score==100) //剪枝
return; //100分不是符合要求的答题情况，所以ans不用加1
}
if(score==70) ans++; //70分，答案加1
if(x==30) return; //共30题，剪枝
dfs(x+1,score,0); //继续做题。0: 答错了
dfs(x+1,score,1); //继续做题。1：答对了
}
int main(){
dfs(0,0,0);
cout<<ans;
}
代码的计算量有多大？第13、14行继续做2次dfs，计算复杂度是。当n=30时，约十亿次，运行时间小于1分钟。
这一题出题人考核的就是DFS。故意让n=30，用DFS刚好能1分钟运行结束得到答案。如果n更大一些，运行时间就太长了，DFS就不合适了。
这一题不适合用python，因为python的循环很慢，运行时间极长。
飞机降落
链接 飞机降落
题目看起来似乎可以用贪心求解，请读者思考是否可行。
本题的N很小，计算量不大，可以求N架飞机的全排列，然后逐一验证验证每个全排列，如果有合法的一个全排列就打印YES，如果所有全排列都不合法就打印NO。
求全排列可以用库函数next_permutation()。本题给的时间限制是2秒，最多有10!个全排列，用next_permutation()的代码运行时间正好2秒，勉强通过测试。
next_permutation()的缺点是不能剪枝：必须先求得一个完整全排列，然后再判断这个全排列是否合法。而大部分全排列的前几项就已经不合法了，不用求完整的全排列。
本题更保险的方法是自己写DFS求全排列，可以在验证一个全排列时在中间剪枝，运行时间比next_permutation()短很多，仅有0.1秒。
C++代码。第12行剪枝，如果这架飞机安排不了就跳过它，相当于终止计算这个全排列。
#include <bits/stdc++.h>
using namespace std;
int T[15],D[15],L[15];
int n;
int vis[15],ans;
void dfs(int plane,int time){
if(plane==n){ //n架飞机都安排好了能降落
ans=1;
return;
}
for(int i=0;i<n;i++){
if(!vis[i] && time<=T[i]+D[i]){ //剪枝
int t = time; //t：安排给飞机i的降落时间
if(t<T[i]) t=T[i]; //飞机i还没到，只能等它
vis[i]=1;
dfs(plane+1,t+L[i]);
vis[i]=0;
}
}
}
int main(){
int m; cin >>m; //m是测试组数
while(m--){
cin >> n;
for(int i=0;i<n;++i) cin >> T[i] >> D[i] >> L[i];
ans = 0;
dfs(0,0);
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
java代码
import java.util.Scanner;
public class Main {
private static int[] T;
private static int[] D;
private static int[] L;
private static int n;
private static int[] vis;
private static int ans;
private static void dfs(int plane, int time) {
if(plane == n) {
ans = 1;
return;
}
for(int i = 0; i < n; i++) {
if(vis[i] == 0 && time <= T[i] + D[i]) {
int t = time;
if(t < T[i]) t = T[i];
vis[i] = 1;
dfs(plane + 1, t + L[i]);
vis[i] = 0;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
while(m-- > 0) {
n = scanner.nextInt();
T = new int[n]; D = new int[n]; L = new int[n];
vis = new int[n];
for(int i = 0; i < n; i++) {
T[i] = scanner.nextInt();
D[i] = scanner.nextInt();
L[i] = scanner.nextInt();
}
ans = 0;
dfs(0, 0);
if(ans == 1) System.out.println("YES");
else System.out.println("NO");
}
}
}
python代码
def dfs(plane, time):
global ans
if plane == n:
ans = 1
return
for i in range(n):
if vis[i] == 0 and time <= T[i] + D[i]:
t = time
if t < T[i]: t = T[i]
vis[i] = 1
dfs(plane + 1, t + L[i])
vis[i] = 0
m = int(input())
for _ in range(m):
n = int(input())
T,D,L = [],[],[]
vis = []
for i in range(n):
t, d, l = map(int, input().split())
T.append(t)
D.append(d)
L.append(l)
vis.append(0)
ans = 0
dfs(0, 0)
if ans == 1: print("YES")
else: print("NO")
最大数字
链接 最大数字
要把N变成最大数字，可以用贪心思路依次处理N每一位：先把最高位尽量变成最大的数字，再把次高位尽量变成最大数字，…，等等。
首先明确一点，1号操作和2号操作不要混用，因为它们互相抵消，混用浪费。
如何把最高位尽量变大？设最高位的数字是d。
先试试1号操作，得到最大数字x，x最大能到9。取操作次数t = min(A, 9-d)，其中9-d表示能得到9的次数；如果A次到不了9，就做A次。
再试试2号操作，因为是减1，所以只有能变成9才有意义。如果有B>d，那么可以减d+1次变成9。
其他位也这样处理，直到用完操作次数A和B。
以上过程可以直接模拟，见下面的Java代码。也可以用DFS来实现，见下面的C++和Python代码。
C++代码。dfs(i, v)的参数i表示当前处理到第i位，例如N=123，第一次dfs(0, 0)，i=0表示第0位是1。dfs(i, v)的参数v是已经得到的值，例如第0位的数字1处理完后，1变成9，那么v=9。
#include<bits/stdc++.h>
using namespace std;
char s[20];
long long ans; //ans: 最大值，要用long long
int A,B; //A:1号操作剩余次数 B:2号操作剩余次数
void dfs(int i,long long v){ //i:当前处理到第i位，v:前面已经得到的值
int d = s[i]-'0'; //第i位的数字
if(s[i]){ //如果s[i]为'\0'，处理结束
int t = min(A,9-d); //1操作次数t:最大到9
A -= t; //更新A。如果A=0，也要继续dfs，目的是求值：v*10+d+t
dfs(i+1,v*10+d+t); //这一位最大是x+t。v*10+d+t是到这一位为止的数值
A += t; //恢复现场
if(B>d){ //操作2:可以减到9
B -= d+1; //做d+1次，减到9
dfs(i+1,v*10+9);
B += d+1; //恢复现场
}
}
else ans = max(ans,v); //处理结束，得到这次DFS的最大值
}
int main(){
cin >> s >> A >> B; //数字N按字符串s读入
dfs(0,0); //从N的最高位开始
cout << ans;
return 0;
}
Java代码。直接模拟题意，不用DFS。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s=in.next(); //数字N按字符串读入
int A = in.nextInt();
int B = in.nextInt();
int[] a=new int[s.length()]; //把N的每个数字存到a[]中
for(int i=s.length()-1;i>=0;i--)
a[i]=(s.charAt(i)-'0');
for(int i=0;i<s.length();i++) { //从最高位处理到最低位
if(a[i]-B < 0)
if((a[i]+1<(9-a[i])|| A<9-a[i]) || A<B){
B -= a[i]+1;
a[i] = 9;
}
while(a[i]<9 && A!=0) {
a[i]++;
A--;
}
System.out.print(a[i]); //打印这一位的最大结果
}
}
}
Python代码。用DFS实现，和C++代码一样。
N,A,B=map(int,input().split())
s=list(map(int,str(N)))
def dfs(i,v):
global A,B,ans
if i==len(s):
ans=max(ans,v)
return
d=s[i]
t=min(A,9-d)
A -= t
dfs(i+1,10*v+d+t)
A+=t
if B > d:
B -= d+1
dfs(i+1,10*v+9)
B += d+1
ans=0
dfs(0,0)
print(ans)
买瓜
链接 买瓜
首先注意到评测用例中的n都不大，估计可以用暴力的搜索解决。
第i个瓜有三个选项：完整的瓜重Ai、半个瓜重Ai/2、不要这个瓜。本题简单的做法是对所有的瓜进行组合，每个瓜尝试三个选项。共有种组合，可以通过约50%的测试。用DFS编码求组合。
C++代码。用到一个小技巧，为了避免除2出现小数，改为把m乘2，那么每个瓜的3个选项是：2Ai、Ai、0。
c++代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[40];
int ans=40;
void dfs(int step,int s,int k){ //step:第step个瓜，s:已选中的瓜的总重，k:砍了几刀
if (s > m || k >= ans) return;
if(s==m) {
ans=min(ans,k);
return;
}
if(step==n+1) return;
dfs(step+1,s,k); //不选
dfs(step+1,s+a[step],k+1); //ai，砍了一刀
dfs(step+1,s+a[step]*2,k); //2ai
}
int main(){
cin>>n>>m; m<<=1; //m乘2
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1,0,0);
cout << (ans == 40? -1: ans) << endl;
}
本题100%得分的代码需要用到分治法和二分，请自行搜索题解。
java代码
import java.util.Scanner;
public class Main {
static int n, m;
static int[] a;
static int ans = 40;
public static void dfs(int step, int s, int k) {
if (s > m || k >= ans) return;
if (s == m) {
ans = Math.min(ans, k);
return;
}
if (step == n + 1) return;
dfs(step + 1, s, k);
dfs(step + 1, s + a[step], k + 1);
dfs(step + 1, s + a[step] * 2, k);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt() << 1;
a = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();
dfs(1, 0, 0);
System.out.println(ans == 40 ? -1 : ans);
}
}
python代码
def dfs(step, s, k):
global ans
if s > m or k >= ans: return
if s == m:
ans = min(ans, k)
return
if step == n + 1: return
dfs(step + 1, s, k)
dfs(step + 1, s + a[step], k + 1)
dfs(step + 1, s + a[step] * 2, k)
ans = 40
n, m = map(int, input().split())
m <<= 1
a = [0] * (n + 1)
a[1:] = map(int, input().split())
dfs(1, 0, 0)
print(-1 if ans == 40 else ans)
7. 习题
蓝桥杯题库的DFS题目：
https://www.lanqiao.cn/problems/?first_category_id=1&tags=DFS&sort=difficulty&asc=1
版权声明：本文为博主作者：罗勇军原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_43914593/article/details/135329367
