### 知识点总结
#### 试题1：大脑分区苏醒问题
- **背景介绍**：
- 人类大脑的功能分区及其活动状态。
- 正常人的大脑分区活跃并相互连接；脑病患者的某些分区可能处于“睡眠”状态。
- 研究发现，若“睡眠”分区与其他至少3个活跃分区保持一年连接，则可以苏醒。
- **问题描述**：
- 给定一位所有大脑分区均处于“睡眠”状态的病人。
- 采用新治疗方法使3个分区同时苏醒。
- 任务是计算其他分区全部苏醒所需的年数。
- **输入说明**：
- 第1行：`M` —— 大脑分区总数（3 ≤ M ≤ 26）。
- 第2行：`N` —— 分区间的连接总数。
- 第3行：3个字母，代表刚刚苏醒的分区。
- 第4行：`N`个字符串，每个字符串表示一对相互连接的分区。
- **输出说明**：
- 如果所有分区能全部苏醒，则输出`WAKEUP IN n YEARS`，其中`n`为所需年数。
- 如果不能全部苏醒，则输出`THIS BRAIN NEVER WAKES UP`。
- **解题思路**：
- 构建图结构，节点为分区，边表示连接关系。
- 需要通过图遍历算法（如DFS/BFS）来寻找激活路径。
- 计算每个未激活分区到已激活分区的距离，以判断是否满足条件并更新总年数。
- 考虑到所有分区最终能否被激活的问题，还需要判断图是否连通。
#### 试题2：植物区域划分问题
- **背景介绍**：
- 测绘人员将卫星拍摄的地面遥感图像转换为数值方阵。
- 方阵中的每个元素表示不同类型的植物，质数表示稀有类型，合数表示常见类型。
- **问题描述**：
- 编写程序分析数值方阵，检测稀有植物区和非稀有植物区。
- 区域划分原则：相同类型且相邻的元素属于同一区域。
- **输入说明**：
- 文件中的每个方阵之前有一行正整数，表示方阵的行数。
- 方阵的每一行由空格分隔的正整数组成。
- 文件最后一行为负整数，表示输入结束。
- **输出说明**：
- 对于每个方阵输出其序号、稀有植物区域的数量及每个区域的面积（按升序排列）、非稀有植物区域的数量。
- **解题思路**：
- 使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历每个方阵。
- 标记已访问过的区域以避免重复计算。
- 对于每个区域，统计其面积并分类存储。
- 输出结果遵循指定格式。
#### 试题3：演员分配问题
- **背景介绍**：
- 导演计划拍摄一部电影，预算有限。
- 为了节省成本，考虑让演员兼任多个角色。
- **问题描述**：
- 输入包括男角色、女角色以及各个场景中出现的角色信息。
- 目标是最小化所需的男演员和女演员人数。
- 角色扮演规则：男女角色不能互换；角色一旦确定，不得更换；同时出现在同一场景中的角色必须由不同演员扮演。
- **输入说明**：
- 第1行：三个整数`M`, `F`, `S`，分别表示男角色数、女角色数和场景数。
- 第2行和第3行：男角色和女角色的名字列表。
- 接下来的`S`行：每个场景中出现的角色数量及其名字。
- **输出说明**：
- 输出最小需要的男演员和女演员的人数。
- **解题思路**：
- 将问题抽象为图模型，节点为角色，边表示角色在场景中同时出现的关系。
- 应用最大匹配算法（例如匈牙利算法）求解两组节点（男角色和女角色）间的最大匹配。
- 最大匹配的数量加上未匹配节点的数量即为最小演员数。
