网易互娱2021校园招聘在线笔试－游戏研发工程师（第一批）

一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图，其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。

迷宫的地图是一个由m*n个格子组成的平面图，纵向的上下方向上每列有m个格子，横向的左右方向上每行有n个格子，其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格，则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。

他的目标是收集到这个迷宫里的所有宝箱，因此他给自己在这个迷宫中寻宝制定了如下策略：

1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱，如果有多个就选定最小编号那个，记为k号宝箱；

2. 如果他当前位置无法到达k号宝箱，则收集失败，流程结束；否则，计算出他当前位置到k号宝箱的最短路径长度，并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后，到k号宝箱的最短路径长度是否有缩短，如果有缩短则往这个方向走一格；

3. 如果他当前所在位置有未收集宝箱，就收集这个宝箱。如果所有宝箱已经被收集，则收集完成。否则回到第1步并重复执行。

输入描述：

输入第一行为一个正整数T，表示有T组数据。

每组数据的第一行为两个正整数m和n，分别表示迷宫地图的行数和列数。

接下来有m行，每行有n个字符，表示迷宫地图中这行每一个中的图例表示。图例如下：

#: 障碍格；

*: 冒险者当前位置，为通行格；

0-9: 每个宝箱所在位置，为通行格；

.: 其它通行格

其中冒险者当前位置在一个迷宫地图中是有且仅有一个的。表示宝箱的数字，在一个迷宫地图中最多只会出现一次，且如果有一个k（k>0)号宝箱在迷宫地图中，则k-1号宝箱也必定会在迷宫地图中。

 

数据范围：

对于所有数据，满足1<=T<=5, 1<=m<=50, 1<=n<=50。

输入样例： 3 5 5 0...1 .#.#. ..*.. .#.#. 2...3 5 5 0...1 .#.#. ..*.# .#.#. 2.#.3 5 5 ....1 .#### ..*.. ####. 0.... 输出描述：

对于每一组数据，输出一个正整数。如果冒险者能收集完所有宝箱，则输出他共走了多少格，否则输出-1。

输出样例 16 -1 -1

游戏工程师小明购买了VR设备之后爱上了体感游戏，而最近他把他的业余时间花在了一款叫十字斩的游戏里。当你戴上VR眼镜启动游戏后，先选择一首音乐，然后会发现有一个N*N的方阵呈现在你的眼前，方阵的每个格子上都有一个数字。然后伴随着音乐节拍，你需要按照时机对方阵进行一次十字斩击（同时斩掉一行和一列，而且选好了行列后不能斩到选定行列之外的格子）。斩击完了之后，矩阵会收缩成一个（N-1）*（N-1）的方阵。

特别的，若该次十字斩斩到的格子数字和是本次所有十字可能里最大的，则会获得一个Perfect，如果N次十字斩都是Perfect，则可以获得FullCombo的成就。但小明的心算能力不行，至今还未能获得FullCombo的成就。所幸初始数字方阵与音乐是一一对应的，所以小明可以通过预先计算十字斩的位置然后背下来，游玩的时候根据记忆去进行十字斩位置的选择即可。

小明上了一天班已经不想写代码了，所以他拜托你来写一个程序为他计算出十字斩的方案。

输入描述：

每个输入数据包含一个测试点。

第一行为一个正整数N，方阵的大小。0 < N <= 500

接下来N行，每行有N个数字，第i行第j个数字表示方阵i行j列上的数字是多少，对于每个数字，保证是非负整数且范围在[0, 65535]内。

输入样例： 3 1 0 0 0 10 10 0 10 10 输出描述：

输出N行，每行两个整数n，m，第i行的n，m表示第i次斩击时，斩击第n行和第m列的数字和是最大的。注意如果此时有多种方案，输出n最小的（更小的数字更方便小明记忆），如果还有多种方案，输出m最小的。

而且n、m的坐标是对于当前的（N + 1 – i）大小方阵而言，并不是对于一开始N*N大小的方阵而言，更加详细的说明参见下方样例说明。

输出样例 2 2 1 2 1 1

七星不靠是中国麻将竞赛规则的番种，胡牌时由东南西北中发白7张，外加其他花色的147、258、369不相连的牌型，且没有将牌而组成。

--百度百科

七星不靠中的七星是指：东西南北中发白，也就是牌中必须有这七张。而其它牌按下述的来拼全：

东西南北中发白+147万+258饼+369条

东西南北中发白+147万+258条+369饼

东西南北中发白+147条+258万+369饼

东西南北中发白+147条+258饼+369万

东西南北中发白+147饼+258条+369万

由于胡牌时只需要14张牌，而上述组合均有16张，那么除了东西南北中发白必须有外，其它三色可以随便去掉两张，都可以组成七星不靠。

输入描述：

输入第一行为一个正整数T（T<=1000)，表示有T组数据。

每组数据一行，包含7张牌，每张牌用”XY”表示，X为[1...9]的数字，Y为(“W”,”B”,”T”)中的一个，分别表示万，饼，条。有可能出现同样的"XY"但是数量不会超过4个。

保证数据一定合法。

输入样例： 4 1T 4T 7T 2B 5B 8B 9W 1T 2T 3T 4T 5T 6T 7T 1B 2W 3T 4B 5W 6T 8W 2B 8B 5B 2B 6T 7W 4W 输出描述：

对于每一组数据，输出YES或者NO，分别表示可以或者不可以组成七星不靠。

输出样例 YES NO YES NO

明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统，玩家可以利用手中的资源和材料，来制造武器和道具。例如，玩家如果需要制造一个小木柜，需要3块木板，而制造一块木板，又需要120个木头和2个小树枝，并且需要走到建筑加工台前制作。而采集木头和小树枝又需要一定的时间。

玩了一段时间之后，明明开始好奇在游戏中做什么最花时间。虽然游戏中已经有标明每个物品的制造时间，但是明明更想通过自己的游戏经历来统计实际需要的时间。明明根据自己的操作，记录下了自己游戏中每个操作事件的开始和结束时间，按时间顺序汇总成了一张表，如下所示：

输入描述：

输入中包含多组数据。输入的第一行是一个整数T(T<=100)，表示后续有多少组测试数据。

每组测试数据第一行是一个整数N(N<=100000)，表示记录的行数。随后是N行记录，每行包括3个整数t（030）、e(030)、s(0或1)，表示事件的时间、事件的id，以及开始或结束信息（0表示开始，1表示结束）。这些记录按照时间先后顺序给出，任意两行的时间均不相同。保证任意一个事件仅出现一次开始和一次结束，且开始时间在结束之前。保证子任务一定先于父任务结束。

输入样例： 1 8 1 1 0 5 2 0 10 3 0 20 3 1 25 4 0 40 4 1 1000 2 1 2000 1 1 输出描述：

对于每一组测试数据，输出一个整数，表示自身所花时间最多的事件id。如果有多个满足条件的事件，则输出事件id最小的那个。

输出样例 1