当前位置：首页 > news >正文

DFS：从入门到进阶的刷题指南

news 2025/6/9 13:41:44

一、基础DFS：递归实现、状态标记、回溯

全排列问题

组合问题

子集问题

二、网格DFS：二维矩阵遍历、连通块计数、方向数组

岛屿数量

单词搜索

被围绕的区域

三、记忆化DFS：动态规划+DFS，缓存中间结果

斐波那契数列（记忆化版）

滑雪

不同路径（带障碍）

四、剪枝优化：可行性剪枝、最优性剪枝、预处理优化

N 皇后

数独求解

火柴拼正方形

五、树/图的DFS：前序/中序/后序遍历、路径搜索、回溯

二叉树路径和

二叉搜索树的范围和

图中所有路径

六、状态压缩DFS：用二进制表示状态，减少存储开销

翻转游戏 II

解数独

最短哈密尔顿路径

七、综合难题：DFS+贪心、DFS+二分、DFS+并查集

栅栏问题

黄金图形

切断圆环链

一、基础DFS：递归实现、状态标记、回溯

全排列问题

#include <iostream>
using namespace std;
int n;
int a[15];
bool vis[15];
void dfs(int x)
{if (x > n){for (int i = 1; i <= n; i++){printf("%5d", a[i]);}cout << endl;return;}for (int i = 1; i <= n; i++){if (!vis[i]){vis[i] = true;a[x] = i;dfs(x + 1);vis[i] = false;a[x] = 0;}}
}
int main()
{cin >> n;dfs(1);return 0;
}

组合问题

#include <iostream>
using namespace std;
int n, r;
int a[30];
void dfs(int x, int start)
{if (x > r){for (int i = 1; i <= r; i++){printf("%3d", a[i]);}cout << endl;return;}for (int i = start; i <= n; i++){a[x] = i;dfs(x + 1, i + 1);a[x] = 0;}
}
int main()
{cin >> n >> r;dfs(1, 1);return 0;
}

子集问题

#include <iostream>
using namespace std;
int n;
int a[20];
void dfs(int x)
{if (x > n){for (int i = 1; i <= n; i++){if (a[i] == 1){cout << i << " ";}}cout << endl;return;}for (int i = 1; i <= 2; i++){a[x] = i;dfs(x + 1);a[x] = 0;}
}
int main()
{cin >> n;dfs(1);return 0;
}