这部分覆盖了机试中暴力枚举、BFS、DFS、递归、搜索剪枝五大核心算法是解决 “路径查找、组合计数、迷宫、分治问题” 的关键下面按模块整理成可直接复用的笔记重点区分不同算法的适用场景和优化技巧目录6.1 暴力枚举穷举法核心知识点经典例题ABCD*4DCBA典型应用百鸡问题6.2 广度优先搜索BFS核心知识点经典例题迷宫最短路径DreamJudge 1563完整 C 语言代码纯 C 版替换 C 队列关键说明6.3 递归及其应用核心知识点经典例题 1求 N!阶乘经典例题 2汉诺塔DreamJudge 1082完整 C 语言代码纯 C 版6.4 深度优先搜索DFS核心知识点例题 1迷宫最短路径DFS 版仅小数据可用例题 2石油储藏连通块计数八方向 DFS6.5 搜索剪枝技巧核心知识点典型应用记忆化搜索求斐波那契6.6 终极骗分技巧应急用总结算法选择核心原则关键模板回顾6.1 暴力枚举穷举法核心知识点定义逐个列举所有可能情况按条件筛选答案牺牲时间换答案全面性适用场景解空间小如四位数、百鸡问题无更优算法时使用优化思路缩小枚举范围如 ABCD*4DCBA 中A 只能是 1/2。经典例题ABCD*4DCBA#include stdio.h int main() { // 枚举A(1-9)、B(0-9)、C(0-9)、D(0-9) for (int A 1; A 9; A) { // A不能为0直接缩小范围 for (int B 0; B 9; B) { for (int C 0; C 9; C) { for (int D 0; D 9; D) { int s1 A * 1000 B * 100 C * 10 D; int s2 D * 1000 C * 100 B * 10 A; if (s1 * 4 s2) { printf(%d\n, s1); // 输出2178 } } } } } return 0; }典型应用百鸡问题问题鸡翁一值钱五鸡母一值钱三鸡雏三值钱一。百钱买百鸡求鸡翁、母、雏各几何枚举思路枚举鸡翁 x (0-20)、鸡母 y (0-33)鸡雏 z100-x-y判断 5x3yz/3100 且 z%30。6.2 广度优先搜索BFS核心知识点本质“层序遍历”从起点逐层扩散用队列实现先进先出核心优势天然适合求 “最短路径、最少步数”首次到达终点即为最优解模板要素方向数组上下左右访问标记数组避免重复访问节点结构体存坐标 步数。经典例题迷宫最短路径完整 C 语言代码#include stdio.h #include string.h #define MAXN 105 #define QUEUE_SIZE 10005 // 队列大小适配100*100迷宫 // 方向数组右、下、左、上 int dir[4][2] {0, 1, 1, 0, 0, -1, -1, 0}; // 迷宫地图 char mpt[MAXN][MAXN]; // 访问标记1已访问0未访问 int vis[MAXN][MAXN]; // 节点结构体坐标(x,y) 步数step typedef struct { int x, y; int step; } Node; // 手动实现队列替代C queue Node queue[QUEUE_SIZE]; int front, rear; // 初始化队列 void initQueue() { front rear 0; } // 入队 void enqueue(Node n) { queue[rear] n; rear % QUEUE_SIZE; // 循环队列避免越界 } // 出队 Node dequeue() { Node n queue[front]; front % QUEUE_SIZE; return n; } // 判断队列是否为空 int isEmpty() { return front rear; } // BFS核心函数返回从(sx,sy)到E的最短步数-1表示无法到达 int bfs(int sx, int sy, int h, int w) { memset(vis, 0, sizeof(vis)); initQueue(); // 起点入队 Node start {sx, sy, 0}; enqueue(start); vis[sx][sy] 1; while (!isEmpty()) { Node now dequeue(); // 到达终点返回步数 if (mpt[now.x][now.y] E) { return now.step; } // 遍历四个方向 for (int i 0; i 4; i) { int nx now.x dir[i][0]; int ny now.y dir[i][1]; // 边界检查 可走*或E 未访问 if (nx 1 nx h ny 1 ny w (mpt[nx][ny] * || mpt[nx][ny] E) !vis[nx][ny]) { vis[nx][ny] 1; Node next {nx, ny, now.step 1}; enqueue(next); } } } // 无法到达终点 return -1; } int main() { int h, w; while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); int sx 0, sy 0; // 起点坐标 // 输入迷宫 for (int i 1; i h; i) { scanf(%s, mpt[i] 1); // 从1开始索引避免边界问题 for (int j 1; j w; j) { if (mpt[i][j] S) { sx i; sy j; } } } // 执行BFS并输出结果 int ans bfs(sx, sy, h, w); printf(%d\n, ans); } return 0; }关键说明纯 C 实现队列避免依赖 C 的queue适配机试纯 C 环境坐标从 1 开始简化边界判断无需处理 0 行 0 列循环队列防止队列溢出适配大迷宫。6.3 递归及其应用核心知识点本质将问题分解为 “同类子问题”函数自调用需有终止条件适用场景阶乘、汉诺塔、全排列、分治问题注意事项递归深度不宜过大避免栈溢出。经典例题 1求 N!阶乘#include stdio.h // 递归求阶乘 long long fac(int x) { if (x 0 || x 1) return 1; // 终止条件0!1,1!1 return (long long)x * fac(x - 1); // 强制类型转换避免溢出 } int main() { int n; scanf(%d, n); printf(%lld\n, fac(n)); return 0; }经典例题 2汉诺塔DreamJudge 1082完整 C 语言代码纯 C 版#include stdio.h int step 0; // 记录移动步数 // 汉诺塔递归函数将n个盘子从a移到c借助b void hanoi(int n, char a, char b, char c) { if (n 1) { // 输出移动步骤 printf(%c--%c, a, c); step; // 每5步换行否则输出三个空格 if (step % 5 0) { printf(\n); } else { printf( ); } return; } // 1. 将n-1个盘子从a移到b借助c hanoi(n - 1, a, c, b); // 2. 将第n个盘子从a移到c hanoi(1, a, b, c); // 3. 将n-1个盘子从b移到c借助a hanoi(n - 1, b, a, c); } int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; step 0; hanoi(n, A, B, C); // 最后补换行若步数不是5的倍数 if (step % 5 ! 0) { printf(\n); } } return 0; }6.4 深度优先搜索DFS核心知识点本质“一条路走到黑回溯再走另一条”基于递归实现核心优势适合求 “连通块数量、全排列、所有可能路径”核心缺点求最短路径易超时需遍历所有路径模板要素访问标记递归前标记回溯后取消终止条件方向遍历四方向 / 八方向。例题 1迷宫最短路径DFS 版仅小数据可用#include stdio.h #include string.h #define MAXN 105 #define INF 99999999 char mpt[MAXN][MAXN]; int vis[MAXN][MAXN]; int dir[4][2] {1,0,0,-1,-1,0,0,1}; int ans; // 存储最短步数 int h, w; // 迷宫高宽 // DFS函数当前坐标(x,y)已走步数step void dfs(int x, int y, int step) { // 最优性剪枝当前步数≥已知最短无需继续 if (step ans) return; // 到达终点更新最短步数 if (mpt[x][y] E) { if (step ans) ans step; return; } // 遍历四个方向 for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 边界可走未访问 if (nx 1 nx h ny 1 ny w (mpt[nx][ny] * || mpt[nx][ny] E) !vis[nx][ny]) { vis[nx][ny] 1; // 标记访问 dfs(nx, ny, step 1); vis[nx][ny] 0; // 回溯取消标记 } } } int main() { while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); memset(vis, 0, sizeof(vis)); int sx 0, sy 0; for (int i 1; i h; i) { scanf(%s, mpt[i] 1); for (int j 1; j w; j) { if (mpt[i][j] S) { sx i; sy j; } } } ans INF; vis[sx][sy] 1; dfs(sx, sy, 0); printf(%d\n, ans INF ? -1 : ans); } return 0; }例题 2石油储藏连通块计数八方向 DFS#include stdio.h #include string.h #define MAXN 105 char mpt[MAXN][MAXN]; int vis[MAXN][MAXN]; // 八方向上下左右 四个对角线 int dir[8][2] {1,0,0,-1,-1,0,0,1,1,1,1,-1,-1,1,-1,-1}; int h, w; // DFS遍历连通块 void dfs(int x, int y) { vis[x][y] 1; // 标记已访问 for (int i 0; i 8; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 边界是石油()未访问 if (nx 1 nx h ny 1 ny w mpt[nx][ny] !vis[nx][ny]) { dfs(nx, ny); } } } int main() { while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); memset(vis, 0, sizeof(vis)); // 输入迷宫 for (int i 1; i h; i) { scanf(%s, mpt[i] 1); } int count 0; // 石油块数量 // 遍历所有格子 for (int i 1; i h; i) { for (int j 1; j w; j) { // 未访问且是石油计数1并遍历连通块 if (!vis[i][j] mpt[i][j] ) { count; dfs(i, j); } } } printf(%d\n, count); } return 0; }6.5 搜索剪枝技巧核心知识点剪枝是搜索的 “优化灵魂”核心是 “提前终止无效搜索”常用类型表格剪枝类型核心逻辑适用场景可行性剪枝当前路径不合法如越界、撞墙直接 return所有搜索基础剪枝最优性剪枝当前步数≥已知最优解无需继续DFS 求最短路径、最小代价记忆化搜索存储已计算的状态结果避免重复计算类似 DP重复子问题多的场景如斐波那契搜索顺序剪枝优先搜索 “更可能出解” 的方向如从已知信息多的位置开始组合枚举、迷宫搜索典型应用记忆化搜索求斐波那契#include stdio.h #include string.h #define MAXN 1000 long long memo[MAXN]; // 记忆化数组存储已计算的斐波那契值 // 记忆化搜索求斐波那契第n项 long long fib(int n) { if (n 2) return 1; if (memo[n] ! -1) return memo[n]; // 已计算直接返回 // 未计算递归求解并存储 memo[n] fib(n-1) fib(n-2); return memo[n]; } int main() { memset(memo, -1, sizeof(memo)); // 初始化记忆数组为-1未计算 int n; scanf(%d, n); printf(%lld\n, fib(n)); return 0; }6.6 终极骗分技巧应急用仅适用于 “想不出正解、搜索超时” 的场景机试应急使用预处理提前计算小范围结果直接查表空间换时间暴力剪枝限制递归深度如 DFS 只递归 10 层放弃部分解贪心辅助优先搜索 “大概率出解” 的方向如迷宫优先向终点方向概率采样随机选几个方向搜索放弃全量遍历正确率看运气。总结算法选择核心原则求最短路径 / 最少步数→ 优先 BFSDFS 易超时求连通块数量 / 所有路径→ 优先 DFS解空间小→ 暴力枚举分治问题阶乘、汉诺塔→ 递归搜索超时→ 加剪枝可行性 / 最优性 / 记忆化。关键模板回顾BFS队列 方向数组 访问标记层序遍历求最短路径DFS递归 回溯 访问标记适合连通块 / 全排列递归终止条件 子问题分解如汉诺塔三步法剪枝提前终止无效路径是搜索优化的核心。掌握这些模板和技巧机试中 80% 的枚举 / 搜索类题目都能解决重点区分 BFS 和 DFS 的适用场景避免用 DFS 求最短路径导致超时。
枚举 / 搜索类算法（机试核心考点）
这部分覆盖了机试中暴力枚举、BFS、DFS、递归、搜索剪枝五大核心算法是解决 “路径查找、组合计数、迷宫、分治问题” 的关键下面按模块整理成可直接复用的笔记重点区分不同算法的适用场景和优化技巧目录6.1 暴力枚举穷举法核心知识点经典例题ABCD*4DCBA典型应用百鸡问题6.2 广度优先搜索BFS核心知识点经典例题迷宫最短路径DreamJudge 1563完整 C 语言代码纯 C 版替换 C 队列关键说明6.3 递归及其应用核心知识点经典例题 1求 N!阶乘经典例题 2汉诺塔DreamJudge 1082完整 C 语言代码纯 C 版6.4 深度优先搜索DFS核心知识点例题 1迷宫最短路径DFS 版仅小数据可用例题 2石油储藏连通块计数八方向 DFS6.5 搜索剪枝技巧核心知识点典型应用记忆化搜索求斐波那契6.6 终极骗分技巧应急用总结算法选择核心原则关键模板回顾6.1 暴力枚举穷举法核心知识点定义逐个列举所有可能情况按条件筛选答案牺牲时间换答案全面性适用场景解空间小如四位数、百鸡问题无更优算法时使用优化思路缩小枚举范围如 ABCD*4DCBA 中A 只能是 1/2。经典例题ABCD*4DCBA#include stdio.h int main() { // 枚举A(1-9)、B(0-9)、C(0-9)、D(0-9) for (int A 1; A 9; A) { // A不能为0直接缩小范围 for (int B 0; B 9; B) { for (int C 0; C 9; C) { for (int D 0; D 9; D) { int s1 A * 1000 B * 100 C * 10 D; int s2 D * 1000 C * 100 B * 10 A; if (s1 * 4 s2) { printf(%d\n, s1); // 输出2178 } } } } } return 0; }典型应用百鸡问题问题鸡翁一值钱五鸡母一值钱三鸡雏三值钱一。百钱买百鸡求鸡翁、母、雏各几何枚举思路枚举鸡翁 x (0-20)、鸡母 y (0-33)鸡雏 z100-x-y判断 5x3yz/3100 且 z%30。6.2 广度优先搜索BFS核心知识点本质“层序遍历”从起点逐层扩散用队列实现先进先出核心优势天然适合求 “最短路径、最少步数”首次到达终点即为最优解模板要素方向数组上下左右访问标记数组避免重复访问节点结构体存坐标 步数。经典例题迷宫最短路径完整 C 语言代码#include stdio.h #include string.h #define MAXN 105 #define QUEUE_SIZE 10005 // 队列大小适配100*100迷宫 // 方向数组右、下、左、上 int dir[4][2] {0, 1, 1, 0, 0, -1, -1, 0}; // 迷宫地图 char mpt[MAXN][MAXN]; // 访问标记1已访问0未访问 int vis[MAXN][MAXN]; // 节点结构体坐标(x,y) 步数step typedef struct { int x, y; int step; } Node; // 手动实现队列替代C queue Node queue[QUEUE_SIZE]; int front, rear; // 初始化队列 void initQueue() { front rear 0; } // 入队 void enqueue(Node n) { queue[rear] n; rear % QUEUE_SIZE; // 循环队列避免越界 } // 出队 Node dequeue() { Node n queue[front]; front % QUEUE_SIZE; return n; } // 判断队列是否为空 int isEmpty() { return front rear; } // BFS核心函数返回从(sx,sy)到E的最短步数-1表示无法到达 int bfs(int sx, int sy, int h, int w) { memset(vis, 0, sizeof(vis)); initQueue(); // 起点入队 Node start {sx, sy, 0}; enqueue(start); vis[sx][sy] 1; while (!isEmpty()) { Node now dequeue(); // 到达终点返回步数 if (mpt[now.x][now.y] E) { return now.step; } // 遍历四个方向 for (int i 0; i 4; i) { int nx now.x dir[i][0]; int ny now.y dir[i][1]; // 边界检查 可走*或E 未访问 if (nx 1 nx h ny 1 ny w (mpt[nx][ny] * || mpt[nx][ny] E) !vis[nx][ny]) { vis[nx][ny] 1; Node next {nx, ny, now.step 1}; enqueue(next); } } } // 无法到达终点 return -1; } int main() { int h, w; while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); int sx 0, sy 0; // 起点坐标 // 输入迷宫 for (int i 1; i h; i) { scanf(%s, mpt[i] 1); // 从1开始索引避免边界问题 for (int j 1; j w; j) { if (mpt[i][j] S) { sx i; sy j; } } } // 执行BFS并输出结果 int ans bfs(sx, sy, h, w); printf(%d\n, ans); } return 0; }关键说明纯 C 实现队列避免依赖 C 的queue适配机试纯 C 环境坐标从 1 开始简化边界判断无需处理 0 行 0 列循环队列防止队列溢出适配大迷宫。6.3 递归及其应用核心知识点本质将问题分解为 “同类子问题”函数自调用需有终止条件适用场景阶乘、汉诺塔、全排列、分治问题注意事项递归深度不宜过大避免栈溢出。经典例题 1求 N!阶乘#include stdio.h // 递归求阶乘 long long fac(int x) { if (x 0 || x 1) return 1; // 终止条件0!1,1!1 return (long long)x * fac(x - 1); // 强制类型转换避免溢出 } int main() { int n; scanf(%d, n); printf(%lld\n, fac(n)); return 0; }经典例题 2汉诺塔DreamJudge 1082完整 C 语言代码纯 C 版#include stdio.h int step 0; // 记录移动步数 // 汉诺塔递归函数将n个盘子从a移到c借助b void hanoi(int n, char a, char b, char c) { if (n 1) { // 输出移动步骤 printf(%c--%c, a, c); step; // 每5步换行否则输出三个空格 if (step % 5 0) { printf(\n); } else { printf( ); } return; } // 1. 将n-1个盘子从a移到b借助c hanoi(n - 1, a, c, b); // 2. 将第n个盘子从a移到c hanoi(1, a, b, c); // 3. 将n-1个盘子从b移到c借助a hanoi(n - 1, b, a, c); } int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; step 0; hanoi(n, A, B, C); // 最后补换行若步数不是5的倍数 if (step % 5 ! 0) { printf(\n); } } return 0; }6.4 深度优先搜索DFS核心知识点本质“一条路走到黑回溯再走另一条”基于递归实现核心优势适合求 “连通块数量、全排列、所有可能路径”核心缺点求最短路径易超时需遍历所有路径模板要素访问标记递归前标记回溯后取消终止条件方向遍历四方向 / 八方向。例题 1迷宫最短路径DFS 版仅小数据可用#include stdio.h #include string.h #define MAXN 105 #define INF 99999999 char mpt[MAXN][MAXN]; int vis[MAXN][MAXN]; int dir[4][2] {1,0,0,-1,-1,0,0,1}; int ans; // 存储最短步数 int h, w; // 迷宫高宽 // DFS函数当前坐标(x,y)已走步数step void dfs(int x, int y, int step) { // 最优性剪枝当前步数≥已知最短无需继续 if (step ans) return; // 到达终点更新最短步数 if (mpt[x][y] E) { if (step ans) ans step; return; } // 遍历四个方向 for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 边界可走未访问 if (nx 1 nx h ny 1 ny w (mpt[nx][ny] * || mpt[nx][ny] E) !vis[nx][ny]) { vis[nx][ny] 1; // 标记访问 dfs(nx, ny, step 1); vis[nx][ny] 0; // 回溯取消标记 } } } int main() { while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); memset(vis, 0, sizeof(vis)); int sx 0, sy 0; for (int i 1; i h; i) { scanf(%s, mpt[i] 1); for (int j 1; j w; j) { if (mpt[i][j] S) { sx i; sy j; } } } ans INF; vis[sx][sy] 1; dfs(sx, sy, 0); printf(%d\n, ans INF ? -1 : ans); } return 0; }例题 2石油储藏连通块计数八方向 DFS#include stdio.h #include string.h #define MAXN 105 char mpt[MAXN][MAXN]; int vis[MAXN][MAXN]; // 八方向上下左右 四个对角线 int dir[8][2] {1,0,0,-1,-1,0,0,1,1,1,1,-1,-1,1,-1,-1}; int h, w; // DFS遍历连通块 void dfs(int x, int y) { vis[x][y] 1; // 标记已访问 for (int i 0; i 8; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 边界是石油()未访问 if (nx 1 nx h ny 1 ny w mpt[nx][ny] !vis[nx][ny]) { dfs(nx, ny); } } } int main() { while (scanf(%d%d, h, w) ! EOF) { if (h 0 w 0) break; memset(mpt, 0, sizeof(mpt)); memset(vis, 0, sizeof(vis)); // 输入迷宫 for (int i 1; i h; i) { scanf(%s, mpt[i] 1); } int count 0; // 石油块数量 // 遍历所有格子 for (int i 1; i h; i) { for (int j 1; j w; j) { // 未访问且是石油计数1并遍历连通块 if (!vis[i][j] mpt[i][j] ) { count; dfs(i, j); } } } printf(%d\n, count); } return 0; }6.5 搜索剪枝技巧核心知识点剪枝是搜索的 “优化灵魂”核心是 “提前终止无效搜索”常用类型表格剪枝类型核心逻辑适用场景可行性剪枝当前路径不合法如越界、撞墙直接 return所有搜索基础剪枝最优性剪枝当前步数≥已知最优解无需继续DFS 求最短路径、最小代价记忆化搜索存储已计算的状态结果避免重复计算类似 DP重复子问题多的场景如斐波那契搜索顺序剪枝优先搜索 “更可能出解” 的方向如从已知信息多的位置开始组合枚举、迷宫搜索典型应用记忆化搜索求斐波那契#include stdio.h #include string.h #define MAXN 1000 long long memo[MAXN]; // 记忆化数组存储已计算的斐波那契值 // 记忆化搜索求斐波那契第n项 long long fib(int n) { if (n 2) return 1; if (memo[n] ! -1) return memo[n]; // 已计算直接返回 // 未计算递归求解并存储 memo[n] fib(n-1) fib(n-2); return memo[n]; } int main() { memset(memo, -1, sizeof(memo)); // 初始化记忆数组为-1未计算 int n; scanf(%d, n); printf(%lld\n, fib(n)); return 0; }6.6 终极骗分技巧应急用仅适用于 “想不出正解、搜索超时” 的场景机试应急使用预处理提前计算小范围结果直接查表空间换时间暴力剪枝限制递归深度如 DFS 只递归 10 层放弃部分解贪心辅助优先搜索 “大概率出解” 的方向如迷宫优先向终点方向概率采样随机选几个方向搜索放弃全量遍历正确率看运气。总结算法选择核心原则求最短路径 / 最少步数→ 优先 BFSDFS 易超时求连通块数量 / 所有路径→ 优先 DFS解空间小→ 暴力枚举分治问题阶乘、汉诺塔→ 递归搜索超时→ 加剪枝可行性 / 最优性 / 记忆化。关键模板回顾BFS队列 方向数组 访问标记层序遍历求最短路径DFS递归 回溯 访问标记适合连通块 / 全排列递归终止条件 子问题分解如汉诺塔三步法剪枝提前终止无效路径是搜索优化的核心。掌握这些模板和技巧机试中 80% 的枚举 / 搜索类题目都能解决重点区分 BFS 和 DFS 的适用场景避免用 DFS 求最短路径导致超时。
