图森未来2020校招笔试卷（二）
时长:120分钟 总分:100分
255浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 4 |
1.
服务器布局
图森未来最近购入了一批服务器，它们大小分别是2*4、4*8、8*16、……、(2^k)*(2^(k+1))，即每台服务器都恰好可以被四台比它们更小的服务器代替。
现在，公司的员工小图被分配了一个任务，那就是根据小森给出的服务器分配方式文档安排服务器的位置。
简而言之，在这个文档中：
输入描述： 输入为符合题目描述中条件的一个文档。
文档保证：
- 第1层级即最高层级有且仅有四个元素；
- 对任意正整数k>=1，每个第k层级的元素下：或者没有嵌套元素但有一个"O"、"X"之一的标签，或者有且仅有四个k+1层级的嵌套元素；
- 任何层级下的四个元素都分别为"NW"、"NE"、"SW"和"SE"中的一个，不会缺少也不会重复；
- 最深的层级不会超过8。输入样例： NE: O NW: X SW: O SE: NE: O NW: NE: O NW: X SW: X SE: O SW: O SE: X 输出描述： 输出为符合题目描述中条件的字符图案。输出样例 +---------------+---------------+ | | | | | | | | | | X | O | | | | | | | | | | +---------------+---+---+-------+ | | X | O | | | +---+---+ O | | | X | O | | | O +---+---+-------+ | | | | | | O | X | | | | | +---------------+-------+-------+
现在，公司的员工小图被分配了一个任务，那就是根据小森给出的服务器分配方式文档安排服务器的位置。
小森交给小图的文档见输入样例。这个文档遵循简化的yaml格式，但是你不需要提前知道什么是yaml。
简而言之，在这个文档中：
- 每一行都以两个字母和一个半角冒号开头，字母是"NW"、"NE"、"SW"、"SE"中的一个，且在同一层级不会重复；
- "NW"、"NE"、"SW"和"SE"分别代表当前层级的左上角、右上角、左下角和右下角位置，即上方为北，右方为东；
- 若冒号后有一个空格和"O"、"X"中的一个字母，则表示这一行是当前层级的一台服务器；
- 若冒号后没有任何内容（即冒号后是换行符），则接下来的若干行一定比当前行多两个空格的缩进，且被缩进的行除缩进外也符合以上全部规则；
- 缩进可以嵌套。
- 最深层级的服务器大小一定是2*4，在图中用一个3行5列的矩阵表示；
- 相邻的服务器会共享同一条相邻边；
- 除了最深层级的服务器，每一台服务器的大小都与它下一层级的四台服务器以2*2的方式拼接起来相同；
- 所有服务器的角落都用加号"+"表示，除此之外所有服务器的水平边界用减号"-"表示，垂直边界用竖线"|"表示，服务器的正中心位置根据文档内容用"X"或"O"中的一个字符表示，其它位置用空格表示。
输入描述： 输入为符合题目描述中条件的一个文档。
文档保证：
- 第1层级即最高层级有且仅有四个元素；
- 对任意正整数k>=1，每个第k层级的元素下：或者没有嵌套元素但有一个"O"、"X"之一的标签，或者有且仅有四个k+1层级的嵌套元素；
- 任何层级下的四个元素都分别为"NW"、"NE"、"SW"和"SE"中的一个，不会缺少也不会重复；
- 最深的层级不会超过8。输入样例： NE: O NW: X SW: O SE: NE: O NW: NE: O NW: X SW: X SE: O SW: O SE: X 输出描述： 输出为符合题目描述中条件的字符图案。输出样例 +---------------+---------------+ | | | | | | | | | | X | O | | | | | | | | | | +---------------+---+---+-------+ | | X | O | | | +---+---+ O | | | X | O | | | O +---+---+-------+ | | | | | | O | X | | | | | +---------------+-------+-------+
2.
卡车牌照（两个方向二选一作答，Python）
小森今天接到了一个任务，要为图森未来在图森市（Tucson）的卡车更换牌照。
因为图森市的特殊规定，合法的车牌号都要满足：
- 车牌号共有六位；
- 车牌号的每一位都是一个0-9中的数字；
- 车牌号组成的六位数（可以包含前导0，如000017即为17）是一个素数。
一次合法的更换是：某个合法的车牌号ABCDEF通过替换其中的一个数字（例如E）变成一个新的车牌号（ABCDXF），且新的车牌号也要是合法的。
现在小森想知道，给出任意两个合法的车牌号，前者最少通过多少次合法的更换可以变成后者？
输入描述： 输出的第一行是一个小于等于5的正整数n，表示测试数据的组数。
接下来的n行每行包含两个六位（可能包含前导0）的正整数，为两个合法的车牌号。输入样例： 1 134503 834703 输出描述： 输出包含n行，每行有一个整数，表示对于每一组数据最少的合法更换的次数。
如果某组数据不存在一种可以合法更换车牌号的方式，在对应行输出-1。输出样例 2
3.
卡车牌照（两个方向二选一作答，非Python）
小森今天接到了一个任务，要为图森未来在图森市（Tucson）的卡车更换牌照。
因为图森市的特殊规定，合法的车牌号都要满足：
- 车牌号共有六位；
- 车牌号的每一位都是一个0-9中的数字；
- 车牌号组成的六位数（可以包含前导0，如000017即为17）是一个素数。
一次合法的更换是：某个合法的车牌号ABCDEF通过替换其中的一个数字（例如E）变成一个新的车牌号（ABCDXF），且新的车牌号也要是合法的。
现在小森想知道，给出任意两个合法的车牌号，前者最少通过多少次合法的更换可以变成后者？ 输入描述： 输出的第一行是一个小于等于100的正整数n，表示测试数据的组数。
接下来的n行每行包含两个六位（可能包含前导0）的正整数，为两个合法的车牌号。输入样例： 1 134503 834703 输出描述： 输出包含n行，每行有一个整数，表示对于每一组数据最少的合法更换的次数。
如果某组数据不存在一种可以合法更换车牌号的方式，在对应行输出-1。输出样例 2
4.
寻找十字
小图最近非常喜欢玩一个游戏。游戏的规则是，在一个n*m大小的0/1矩阵中，找到如下的图形：
?1?
111
111
?1?
其中?位置可以是0也可以是1。
游戏中，小图需要指出在给出的0/1矩阵中这个图形出现在了多少个不同的位置。
现在他希望你可以写一个程序帮助他计算这个值。
输入描述：
输入的第一行是两个正整数n, m，1 <= n, m <= 1000。接下来的n行，每行有m个字符，每个字符是0或1中的一个，表示了整个0/1矩阵。输入样例： 5 5 01000 11100 11101 11111 00101 输出描述： 输出只包含一个正整数，为输入的0/1矩阵中有多少个不同位置的上述图形。输出样例 3
