图森未来2020校招笔试卷（一）
时长:120分钟 总分:100分
270浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
旋转数字
小图（Tu）和小森（Simple）最近发现了一个有趣的游戏。
123 -> 231 -> 312 -> 123 -> ...
在这之后，他们需要把每一个数字依次接到前一个数字最高位的前面，构成一列无限长的数字。例如，对于上面的例子，构成的数字是：
... 231123312231123312231123
假设小森拿到的数字是31321，那么他构成的数字是：
... 1313221313321311321331321
接下来，他们会选择一个k值，并比较他们自己数字的后k位，较大的人会赢得最终的胜利。
小图和小森有他们进行的若干局游戏的记录，每局游戏都记录了t、s和k的值。他们希望知道，在这些游戏中，分别是谁获得了胜利？
输入描述： 输入的第一行是一个n(1 <= n <= 104)，表示游戏进行的局数。
在游戏的一开始，小图和小森会分别获得一个初始数字t和s，10 < t, s < 109。之后，他们会从初始数字开始，不停地将自己数字的第一位移动到最后一位。
例如，初始数字是123的时候，数字的变化是：
在这之后，他们需要把每一个数字依次接到前一个数字最高位的前面，构成一列无限长的数字。例如，对于上面的例子，构成的数字是：
... 231123312231123312231123
假设小森拿到的数字是31321，那么他构成的数字是：
... 1313221313321311321331321
接下来，他们会选择一个k值，并比较他们自己数字的后k位，较大的人会赢得最终的胜利。
小图和小森有他们进行的若干局游戏的记录，每局游戏都记录了t、s和k的值。他们希望知道，在这些游戏中，分别是谁获得了胜利？
输入描述： 输入的第一行是一个n(1 <= n <= 104)，表示游戏进行的局数。
接下来的n行中每行有三个数，依次为题目中的t、s和k(10 < t, s < 109, 1 <= k <= 109)。
为了方便计算，小图和小森的初始数字（t、s）的所有数位都不是0。
输入样例：
3
123 31321 1
123 31321 3
123 31321 9
输出描述：
输出包含n行，每一行是"Tu"、"Simple"和"Draw"中的一个字符串（不含引号），表示胜利者是谁，或者是平局。输出样例
Tu
Simple
Simple
2.
迷宫难题
图森未来的自动驾驶小卡车今天被派到了一个陌生的迷宫内部运输一些货物。
工程师小图已经提前拿到了这个迷宫的地图，地图是一个n*m的字符矩阵，上面包含四种不同的字符："."，"#"，"S"和"E"。其中"S"和"E"分别代表运货的起点和终点，"."为可行驶区域，"#"为不可行驶区域。每个可行驶区域都可以移动到上、下、左、右相邻的可行驶区域，且四种移动的距离都为1。
为了估算运输的成本，小图希望你可以帮助他计算从起点到终点的最短行驶距离。
而输入样例2，因为多出了一条直接从S到E的路径，所以最短行驶距离会减少到7。
输入描述： 第一行有两个正整数，分别为n和m（2 <= n, m <= 1000），为数据的行数和列数。
接下来的n行，每行包含m个字符，构成了整张地图。地图中只包含"."，"#"，"S"和"E"四种字符，且"S"和"E"都会且仅会出现一次。输入样例： 6 10 ########## #........# #.######.# #.######.# #.######.# #S######E# 输出描述： 输出一个正整数，为从起点到终点最短行驶距离的长度。输出样例 15
工程师小图已经提前拿到了这个迷宫的地图，地图是一个n*m的字符矩阵，上面包含四种不同的字符："."，"#"，"S"和"E"。其中"S"和"E"分别代表运货的起点和终点，"."为可行驶区域，"#"为不可行驶区域。每个可行驶区域都可以移动到上、下、左、右相邻的可行驶区域，且四种移动的距离都为1。
为了估算运输的成本，小图希望你可以帮助他计算从起点到终点的最短行驶距离。
例如，对于下方的输入样例1，从起点到终点有且仅有一条路径，路径的长度为15（最开始卡车在S的位置，需要经过15次移动才能到达E的位置）。所以，最短行驶距离也为15。
而输入样例2，因为多出了一条直接从S到E的路径，所以最短行驶距离会减少到7。
输入描述： 第一行有两个正整数，分别为n和m（2 <= n, m <= 1000），为数据的行数和列数。
接下来的n行，每行包含m个字符，构成了整张地图。地图中只包含"."，"#"，"S"和"E"四种字符，且"S"和"E"都会且仅会出现一次。输入样例： 6 10 ########## #........# #.######.# #.######.# #.######.# #S######E# 输出描述： 输出一个正整数，为从起点到终点最短行驶距离的长度。输出样例 15
3.
简单卷积
小森最近在工作上遇到了一些麻烦，他需要在许多矩阵上计算卷积的结果，希望你能够帮助他写一个程序简化计算。
小森已经将他要计算的卷积处理成了如下的简化形式，以便即使不了解卷积的人也可以进行计算：
给出一个n*m的矩阵A和一个3*3的矩阵B，A和B的计算结果是一个(n-2)*(m-2)的矩阵C，满足：
请按照以上公式，根据给出的矩阵A和B计算出矩阵C。
输入描述：
输入的第一行为两个正整数n和m，其中3 <= n, m <= 500。
接下来的n行，每行包含m个用空格分隔的整数，其中第x行第y列的整数为
，且
。
，且。接下来的3行，每行包含3个用空格分隔的整数，其中第x行第y列的整数为
，且
。
输入样例：
4 4
1 2 3 4
5 4 3 2
-1 -2 -3 -4
-5 -4 -3 -2
1 0 -1
0 -1 1
-1 0 1 输出描述：
输出包含n-2行，每行包含m-2个用空格分隔的整数，其中第x行第y列的整数为，且。
。输出样例
-5 -5
3 3