题目 抽奖1 抽奖2 抽奖3 抽奖4 迷宫的相邻点 迷宫之判定 迷宫之方案数
抽奖1
题目大意
从编号为 1、2、3 的小球中 有放回地抽取 3 次,输出所有可能的抽取结果,并按字典序输出。
题意分析
* 有放回,意味着每次都可以抽 1、2、3 中任意一个;
* 抽取 3 次,总共有 33=273^3 = 2733=27 种组合;
* 每组输出一个序列,共 3 个数,按字典序排序。
解题思路
* 每个位置都可以是 1、2、3;
* 用三重循环枚举所有可能;
* 因为 1 到 3 本身就是有序的,按顺序枚举自然满足字典序。
时间复杂度解析
* 总共 33=273^3 = 2733=27 种情况;
* 每种情况输出 3 个数;
* 所以时间复杂度为 O(1)O(1)O(1),极小,直接枚举即可。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
抽奖2
题目大意
给定一个整数 nnn,表示有编号为 111 到 nnn 的 nnn 个球,每次从中有放回地抽一个球,共抽 nnn 次。请你输出所有可能的抽取情况,要求按字典序输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每一轮抽奖都可以选 111 到 nnn 中的任意一个数字。
* 有放回:意味着每一位都可以独立选择 nnn 个数。
* 抽 nnn 次:每种结果是一个长度为 nnn 的序列。
* 所有可能情况数为 nnn^nnn,在 n=8n=8n=8 时是 167772161677721616777216,可以接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用 递归 DFS 生成所有长度为 nnn 的数字序列,序列中的每个位置可取值范围为 111 到 nnn。
字典序要求:
* 因为我们在递归中从小到大枚举,所以天然满足字典序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
总共有 nnn^nnn 个序列,每个序列长度 nnn,所以时间复杂度是:
* 总复杂度:O(nn)O(n^n)O(nn)
* 对于 n=8n = 8n=8,最多 167772161677721616777216 次递归调用,打印 16M 行,属于可接受范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
抽奖3
题目大意
给定一个整数 nnn,表示有 nnn 个球,编号从 111 到 nnn。每次从中抽取一个球,无放回地抽 nnn 次。求所有可能的抽取情况,按字典序输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 无放回意味着抽取过程中不能重复;
* 抽 nnn 次,恰好把 nnn 个数全排列一遍;
* 输出的本质是 nnn 个数的全排列;
* 字典序输出即为 字典序排列所有全排列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用 DFS+回溯 生成 1∼n1\sim n1∼n 的全排列,每次选择一个未使用的数字,标记为已使用,递归下一位。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 一共 n!n!n! 种情况;
* 每种排列打印 nnn 个数字;
* 所以时间复杂度为 O(n×n!)O(n \times n!)O(n×n!),最大情况 n=8n=8n=8 时是 8×40320=3225608 \times 40320 = 3225608×40320=322560,可接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
抽奖4
题目大意
* 有 nnn 个小球,每个小球有一个积分 a[i]a[i]a[i]。
* 每次可以有放回地抽一个小球,共抽 nnn 次。
* 求所有 编号序列,使得 nnn 次抽取的小球积分总和为 kkk。
* 要求结果按字典序输出,输出的是小球编号序列(从 1 开始编号)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 有放回:每次都可以选任意编号的小球。
* 抽 nnn 次:结果是一个长度为 nnn 的编号序列。
* 要求总积分之和为 kkk,所以需要在枚举的同时记录并判断和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
这是一个典型的 DFS + 剪枝 + 记录编号 的问题:
1. 使用 DFS 每次递归代表一次抽取;
2. 每次可以从 1 到 nnn 中任选一个编号;
3. 记录当前路径和对应的积分和;
4. 当抽满 nnn 次且积分和为 kkk 时,输出当前路径;
5. 需要对编号序列按字典序输出;
* 枚举顺序从小到大自然满足字典序要求;
6. 剪枝优化:
* 当前积分和已经超过 kkk 的时候提前剪枝,避免继续递归。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 理论上最多需要枚举 nnn^nnn 种序列;
* 但我们通过剪枝(提前终止)可以大大减少不必要的递归;
* 对于 n≤8n \le 8n≤8 完全可接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
迷宫的相邻点
题目大意
给定一个 n×mn \times mn×m 的迷宫,以及某个格子坐标 (x,y)(x, y)(x,y),请输出其右、下、左、上方向的相邻格子的坐标。如果越界则输出 NA。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 总共有 4 个方向,按照 右、下、左、上 的顺序输出。
* 每个方向对应一个坐标偏移值 (dx, dy)。
* 若相邻坐标合法(不越界),就输出相邻坐标;
* 若越界,则输出 NA。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
我们可以用一个方向数组来存储方向偏移,例如:
然后依次尝试四个方向,看相邻点是否在迷宫范围内。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
迷宫之判定
题目大意
给定一个 n×mn \times mn×m 的迷宫,其中:
* '.' 表示可以走;
* '#' 表示障碍物,不能走;
问能否从左上角 (0,0) 走到右下角 (n-1,m-1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 每次只能走上下左右 4 个方向;
* 不能走出边界;
* 不能重复走已经走过的格子;
* 不能走障碍物 #;
* 一旦到达终点,即可判断为 “YES”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方向数组
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
迷宫之方案数
题目大意
* 给定一个 N×MN \times MN×M 的迷宫,有 TTT 个障碍点;
* 每个格子最多只能走一次;
* 从起点 (SX,SY)(SX, SY)(SX,SY) 走到终点 (FX,FY)(FX, FY)(FX,FY);
* 求一共有多少条可行路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
输入解析
* 第一行:迷宫大小和障碍数量:N M T
* 第二行:起点和终点坐标:SX SY FX FY
* 接下来 TTT 行:障碍坐标,不能走;
* 所有坐标都是 1 开始,不是 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
这是典型的 DFS 回溯搜索路径数:
* 每次尝试向上/下/左/右走;
* 如果下一个点可走(没越界、不是障碍、没走过)就继续;
* 如果走到了终点,计数器加 1;
* 每次递归后,记得回溯:将当前点恢复“未访问”状态。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现细节
* 用一个 vis[N][M] 数组记录哪些格子已经访问过;
* 用一个 maze[N][M] 数组记录哪些格子是障碍;
* 起点终点都可能在边角,注意边界处理;
* 使用 dx, dy 控制方向遍历。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方向数组
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码实现