一、编程题
1、红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
时间限制：1000
内存限制：65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时，表示输入结束。
输出
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
样例输出
45
参考答案：
无
解析：【喵呜刷题小喵解析】这是一个典型的广度优先搜索（BFS）问题。我们可以使用队列来存储待访问的瓷砖，并使用一个二维数组来标记已经访问过的瓷砖。首先，我们定义一个函数`count_tiles`，它接受三个参数：瓷砖的数量`W`和`H`，以及瓷砖的颜色矩阵`grid`。在函数内部，我们创建一个二维数组`visited`，用于标记已经访问过的瓷砖。然后，我们创建一个队列`queue`，用于存储待访问的瓷砖。队列中的元素是瓷砖的坐标。接下来，我们遍历整个瓷砖矩阵，将初始位置以外的所有黑色瓷砖加入队列。然后，我们进入一个循环，只要队列不为空，就持续进行循环。在每次循环中，我们从队列中取出一个瓷砖，然后遍历它的四个相邻瓷砖。如果相邻瓷砖是黑色的，并且没有被访问过，我们就将其加入队列，并将其标记为已访问。同时，我们增加计数器`count`的值。最后，我们返回计数器`count`的值，即我们能够到达的黑色瓷砖的数量。在主程序中，我们读取输入，直到读取到两个零为止。对于每个数据集合，我们调用`count_tiles`函数，并输出结果。
2、迷宫问题
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
时间限制：1000
内存限制：65536
输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求找出从左上角到右下角的最短路径，可以使用Dijkstra算法来解决。Dijkstra算法是一种用于求解最短路径问题的贪心算法，适用于权值为非负的情况。首先，我们需要初始化起点到自身的距离为0，其他点的距离初始化为无穷大，并将起点标记为已访问。然后，从未访问的点中选择距离起点最近的点，将其标记为已访问，并更新其邻居点的距离。重复这个过程，直到终点被标记为已访问。在代码实现中，我们使用一个二维数组maze来表示迷宫，其中1表示墙壁，0表示可以走的路。我们使用一个二维数组dist来记录起点到每个点的最短距离，使用一个二维数组vis来记录每个点是否被访问过。我们使用一个优先队列pq来存储待访问的点，按照距离起点的距离从小到大排序。在dijkstra函数中，我们首先初始化优先队列pq，将起点加入队列，并初始化距离数组dist和访问数组vis。然后，在循环中，从未访问的点中选择距离起点最近的点，将其标记为已访问，并更新其邻居点的距离。最后，在主函数中，我们输入迷宫，调用dijkstra函数求解最短路径，并输出路径。需要注意的是，在输出路径时，我们需要判断起点和终点是否被访问过，以及当前点是否被访问过。如果当前点是起点或终点，则直接输出坐标；否则，如果当前点没有被访问过，则跳过；否则，输出坐标并加上一个空格。最后，每行输出结束后需要换行。
3、二叉树的深度
给定一棵二叉树，求该二叉树的深度
二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度
时间限制：1000
内存限制：65535
输入
第一行是一个整数n，表示二叉树的结点个数。二叉树结点编号从1到n，根结点为1，n <= 10 接下来有n行，依次对应二叉树的n个节点。 每行有两个整数，分别表示该节点的左儿子和右儿子的节点编号。如果第一个（第二个）数为-1则表示没有左（右）儿子
输出
输出一个整型数，表示树的深度
样例输入
3
2 3
-1 -1
-1 -1
样例输出
2
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求计算二叉树的深度。二叉树的深度是从根结点到最远叶结点的路径上的节点数。首先，我们定义一个函数`max_depth`，它接受两个参数：节点数`n`和父节点到子节点的映射`parent_to_children`。`parent_to_children`是一个列表，其中每个元素都是一个列表，包含父节点的编号和它的左右子节点的编号。如果某个子节点的编号为-1，表示该节点没有子节点。在`max_depth`函数中，我们首先检查节点数是否为0，如果是，则返回0，表示空树的深度为0。然后，我们递归地计算左子树和右子树的深度。如果左子节点存在，我们调用`max_depth`函数来计算左子树的深度，否则返回0。同样地，我们计算右子树的深度。最后，我们返回左子树和右子树深度的较大值加1，加1是因为我们还需要加上根节点。在主程序中，我们首先读取节点数`n`，然后读取每个节点的父节点和子节点的编号，构建`parent_to_children`列表。最后，我们调用`max_depth`函数，以1（根节点的编号）作为参数，计算二叉树的深度，并输出结果。
4、表达式·表达式树·表达式求值
众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：
/ \
a *
/ \
b c
现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制：1000
内存限制：65535
输入
输入分为三个部分。 第一部分为一行，即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。 第二部分为一个整数n(n < 10)，表示中缀表达式的变量数。 第三部分有n行，每行格式为C x，C为变量的字符，x为该变量的值。
输出
输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（\）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，\出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。 第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。
样例输入
a+b*c
3
a 2
b 7
c 5
样例输出
abc*+
+
/ \
a *
/ \
b c
37
参考答案：
无
解析：【喵呜刷题小喵解析】：本题要求将中缀表达式转化为表达式树，并输出其逆波兰式、树形表示和表达式的值。首先，我们需要将中缀表达式转化为逆波兰式。中缀表达式转化为逆波兰式的基本思路是使用一个栈来保存运算符，遍历中缀表达式的每个字符，如果是变量则直接加入结果列表，如果是运算符则弹出栈顶的运算符直到栈为空或该运算符的优先级高于当前运算符，然后将当前运算符入栈。遍历结束后，将栈中剩余的运算符加入结果列表。然后，我们可以利用逆波兰式构建表达式树。首先，我们需要构建一个与逆波兰式等长的节点列表，然后将逆波兰式中的每个字符依次加入节点列表。如果字符是变量，则直接加入；如果字符是运算符，则将其父节点的两个子节点依次加入。最后，我们可以计算表达式的值。首先，我们需要将每个变量的值保存在一个字典中。然后，我们遍历逆波兰式，如果是变量，则直接取出对应的值；如果是运算符，则取出对应的两个子节点的值进行运算，并将结果保存回字典中。最后，返回字典中变量a的值即为表达式的值。注意，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
