一、编程题
1、1.迷宫
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
时间限制：3000
内存限制：65536
输入
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
样例输入
```
2
3
.##
..#
#..0 0 2 2
5
.....###.#
..#..###.....#.0 0 4 0
```
样例输出
```
YES
NO
```
解析：【喵呜刷题小喵解析】：
这个问题可以使用广度优先搜索（BFS）来解决。
首先，读入迷宫的规模n，以及迷宫矩阵。同时，读入起点A和终点B的坐标。
如果起点A或者终点B是墙壁（即对应位置的字符为'#'），则无法从起点走到终点，直接输出"NO"。
否则，使用BFS进行搜索。从起点A开始，将起点A加入队列，并标记为已访问。然后，开始BFS，每次从队列中取出一个点，判断该点是否为终点。如果是，则返回true，表示可以从起点走到终点。否则，将与该点相邻的四个点（东南西北）加入队列，并标记为已访问。
如果搜索完整个迷宫，没有找到终点，则返回false，表示无法从起点走到终点。
在搜索过程中，使用一个二维数组visited来记录每个点是否被访问过，以避免重复访问。同时，使用一个队列q来保存待搜索的点。
最后，输出搜索结果即可。
2、2.拯救公主
多灾多难的公主又被大魔王抓走啦！国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士，同时也是阿福的好伙伴，你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图，上面标记了阿福和公主所在的位置，以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门，通过一个传送门可以瞬间转移到任意一个传送门，当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外，你还查探到公主所在的地方被设下了结界，需要集齐K种宝石才能打开。当然，你在地图上也标记出了不同宝石所在的位置。
你希望阿福能够带着公主早日凯旋。于是在阿福出发之前，你还需要为阿福计算出他最快救出公主的时间。
地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置，字符E表示公主所在的位置，字符#表示不能踏入的禁区，字符$表示传送门，字符.表示该位置安全，数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置，但不能走出地图边界。阿福每走一步需要花费1个单位时间，从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时，就视为得到了该宝石，不需要花费额外时间。
时间限制：1000
内存限制：65536
输入
第一行是一个正整数T（1 <= T <= 10），表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C（2 <= R, C <= 200）和K，表示地图是一个R×C的矩阵，而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内，即不会超过5种宝石。
输出
对于每一组数据，输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
样例输入
```
1
7 8 2
..........S..#0..##..1...0#........1#......##E.....1....```
样例输出
```
11
```
参考答案：根据输入数据，地图大小为7x8，需要收集2种宝石。阿福的起始位置为S，公主的位置为E。地图上有两个传送门，分别位于(1, 1)和(7, 7)。阿福需要收集两种宝石，分别为0和1。最优解为：1. 阿福从起始位置S走到传送门(1, 1)。2. 通过传送门到达另一个传送门(7, 7)。3. 从传送门(7, 7)走到公主所在位置E。阿福总共需要移动10步，每步需要1个单位时间，因此最少需要10个单位时间。但是，阿福在走到公主所在位置E之前，需要先收集两种宝石。宝石0位于(2, 2)，宝石1位于(6, 2)。因此，阿福需要先走到宝石0的位置，再走到宝石1的位置，最后走到公主所在位置E。阿福总共需要移动12步，每步需要1个单位时间，因此最少需要12个单位时间。所以，阿福救出公主所花费的最少单位时间为12。输出结果为：12
解析：【喵呜刷题小喵解析】：
本题是一道动态规划或最短路径问题。需要计算出阿福救出公主的最短时间。由于阿福可以通过传送门瞬间转移，因此我们需要考虑如何最优地使用传送门。
首先，我们需要找到所有传送门的位置，并确定哪些宝石在阿福可以到达的路径上。然后，我们可以使用动态规划或最短路径算法来计算最短时间。
具体步骤如下：
1. 读取输入数据，确定地图大小、宝石数量和地图内容。
2. 遍历地图，找到所有传送门的位置，并确定哪些宝石在阿福可以到达的路径上。
3. 对于每个传送门，计算从当前位置到该传送门的最短时间。
4. 对于每个宝石，计算从当前位置到该宝石的最短时间。
5. 对于每个位置，计算从当前位置到公主所在位置的最短时间，同时考虑是否需要收集宝石。
6. 找到从起始位置到公主所在位置的最短时间，即为答案。
需要注意的是，由于传送门的位置和宝石的位置是随机的，因此我们需要根据具体情况来确定最优解。同时，由于地图的大小和宝石的数量都有限制，因此我们需要考虑算法的时间复杂度和空间复杂度。
3、3.二叉树的深度
给定一棵二叉树，求该二叉树的深度
二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度
时间限制：1000
内存限制：65535
输入
第一行是一个整数n，表示二叉树的结点个数。二叉树结点编号从1到n，根结点为1，n <= 10 接下来有n行，依次对应二叉树的n个节点。 每行有两个整数，分别表示该节点的左儿子和右儿子的节点编号。如果第一个（第二个）数为-1则表示没有左（右）儿子
输出
输出一个整型数，表示树的深度
样例输入
```
3
2 3
-1 -1
-1 -1
```
样例输出
```
2
```
参考答案：```#include
解析：【喵呜刷题小喵解析】：
首先，需要理解二叉树的深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度。
根据题目要求，我们需要先构建二叉树，然后计算二叉树的深度。
构建二叉树时，我们可以使用结构体TreeNode来存储每个节点的值以及左右子节点的编号。然后，根据输入，我们可以为每个节点分配内存，并设置其左右子节点的编号。
计算二叉树的深度时，我们可以使用递归的方法。对于每个节点，我们分别计算其左子树和右子树的深度，然后取两者中的较大值，再加上当前节点，即为该节点的深度。
最后，我们只需要计算根节点的深度，即为整棵二叉树的深度。
在代码实现中，我们使用了C++语言，首先定义了TreeNode结构体，然后实现了maxDepth函数来计算二叉树的深度。在main函数中，我们根据输入构建了二叉树，并计算了二叉树的深度，最后输出结果。
4、4.Sequence
给定m个数字序列，每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列，显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和，一共会得到n^m个和，请找出最小的n个和
时间限制：3000
内存限制：65536
输入
输入的第一行是一个整数T，表示测试用例的数量，接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m（0 < m <= 100）和n(0 < n <= 2000)，然后有m行，每行有n个数，数字之间用空格分开，表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例，输出一行用空格隔开的数，表示最小的n个和
样例输入
```
1
2 3
1 2 3
2 2 3
```
样例输出
```
3 3 4
```
参考答案：对于每个测试用例，首先计算所有序列中所有数字的和，记为total_sum。然后，对于每个序列，将序列中的数字按照从小到大的顺序排序。接着，从每个序列中选取最小的数字，组成一个新的序列，计算这个新序列的和，记为min_sum。重复这个过程n次，每次选取当前序列中除已选取数字外的最小数字，更新min_sum。最后，将得到的n个min_sum按从小到大的顺序输出。
解析：【喵呜刷题小喵解析】：
对于这个问题，我们可以采用贪心的策略。首先，我们需要计算所有序列中所有数字的和，记为total_sum。然后，对于每个序列，将序列中的数字按照从小到大的顺序排序。接着，从每个序列中选取最小的数字，组成一个新的序列，计算这个新序列的和，记为min_sum。由于我们选取的是每个序列中最小的数字，所以新序列的和一定是所有可能的新序列中最小的。重复这个过程n次，每次选取当前序列中除已选取数字外的最小数字，更新min_sum。最后，将得到的n个min_sum按从小到大的顺序输出。
这种方法的时间复杂度是O(m*n*logn)，其中m是序列的数量，n是每个序列中数字的数量。这是因为我们需要对每个序列进行排序，排序的时间复杂度是O(n*logn)，而我们需要对每个测试用例进行m次这样的操作。
另外，这种方法的空间复杂度是O(m*n)，因为我们需要存储每个序列中的数字，以及每次选取的数字。
需要注意的是，这种方法只能保证得到的是最小的n个和，但不能保证得到的是所有可能的新序列中最小的n个和。因为可能存在一些新序列，它们的和虽然比通过这种方法得到的新序列的和要大，但是在所有可能的新序列中的和却是最小的。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
