问题

题目

问题: 给定一个有目标位置和边界单元格为空的 n × n 方格表，找出哪个位于边界单

元格的箭头会击中最多连续的目标而不经过目标之间的任何空单元格。箭头方向为：

(A)←、(B) ↑、 © →、(D) ↓、(E) ↖、 (F) ↗、 (G) ↘ 和 (H) ↙。 将箭头的位置和方向

输出为 3 个字符的字符串。按照行优先的方式，左上角被识别为行 = 0 和列 = 0。示例：

通过检验每个边界位置，从位置（4，0）出发的 C 箭头比任何其他位置有更多的目标可以击中，因为它击中了 2 个目标。从同一位置出发的 F 箭头如果不首先经过从位置（5 , 0）出发，F 一个空单元格，就不能击中任何目标。 箭头将击中一个目标，H 箭头将偏离这个方格表。然后检验其他位置，从位置（5，1）出发的 B 箭头将只击中一个目标，从位置（4，5）出发的 A 箭头也一样。所以输出为 40C 。

输入

将有一个整数表示方格表的大小，另一个字符串表示目标的位置，每个位置由一个空格分隔。我们保证方格表不大于10 × 10。

输出

对于每个方格表，输出一个有 3 个字符的字符串表示箭头的位置和方向，该箭头在不经过任何空单元格的情况下可以击中最多目标。在平局的情况下，输出按 ASCII顺序排在前面的字符串（例如 “05F”< “50A”）。

样本输入

6

13 21 41 42 445

31 21 13 32 11 1210

81 84 86 87 88 71 73 75 77 32 33 45 47 48 11 13 15 168

65 45 55 32 42 54 13 14 41 61 244

12 22 21

样本输出:

40C01D89A05D02D

测试输入

9

11 14 17 33 44 24 31 35 37 45 41 53 57 62 64 66 71 777

15 23 24 32 35 31 45 55 446

43 33 44 14 23 4110

25 71 82 63 54 45 56 75 77 88 21 24 26 27 28 12 13 15 34 35

33 378

12 13 16 21 22 31 34 35 36 45 43 41 52 54 56 66 65 64 63 61

测试输出

80F65B03D29A27H

解答

分析

先判断一个方向的临近第一点，如果有就朝这个方向继续算下一点，如果没有就跳过该方向。最多射中的点是n-2。

程序

# 箭头处在边界位置上，需要判断边界的标号def format_input():"""格式化输出的内容，将输入的字符串转换成数值（整数）:return:n:方格行列数。target_location_list：目标坐标列表。"""n = int(input("请输入：\n")) # 方格大小 n * n# 目标位置target_location_str = input().split(" ") # 通过空格切分为列表# print(target_location_str) # ['13', '21', '41', '42', '44']target_location_list = [list(item) for item in target_location_str] # 将坐标字符串转换成列表# print(target_location_list_str)for i in range(len(target_location_list)): # 将字符串坐标转换成数字坐标target_location_list[i][0] = int(target_location_list[i][0])target_location_list[i][1] = int(target_location_list[i][1])# print(target_location_list)return n, target_location_listdef get_border_location(n):"""根据表格规格得到边界坐标列表。:param n: 表格规格 n * n。:return: border_location_list"""border_location_list = [] # 总的边界点个数应该是：n*2+(n-2)*2for i in range(n):# 第一行border_location_list.append([0, i])# 最后一行border_location_list.append([n-1, i])for i in range(1, n-1):# 最左侧border_location_list.append([i, 0])# 最右侧border_location_list.append([i, n-1])return border_location_listdef move_to_get_step_list(max_add, border_dot, target_location, step_list_list): # 通过移动找到目标路径(射箭后箭经过的路线)"""为了防止get_shout_situation()方法太过冗长，故写此方法，用于在get_shout_situation()方法中调用，找到所有的射箭可用路径。:param max_add: 可能的最多可以射中的目标。:param border_dot: 某一个边界点坐标。:param target_location: 目标位置列表:param step_list_list: 射中目标的路径列表:return: step_list_list：射中目标的路径列表，作为下一个get_shout_situation()方法内的循环运行的move_to_get_step_list()方法的参数"""# A：向左 B：向上 C：向右 D：向下 E：左上 F：右上 G：右下 H：左下# 1. 向左：A : x,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0], border_dot[1] - i] # x,y-1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 2. 向上：B : x-1,ytemp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1]] # x-1,yif assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 3. 向左：C : x,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0], border_dot[1] + i] # x,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 4. 向下：D : x+1,ytemp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1]] # x+1,yif assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 5. 向左上：E : x-1,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1] - i] # x-1,y-1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 6. 向右上：F : x-1,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1] + i] # x-1,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 7. 向右下：G : x+1,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1] + i] # x+1,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 8. 向左下：H : x+1,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1] - i] # x+1,y-1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:breakreturn step_list_listdef get_coordinate_direction_str_by_coordinate_list(coordinate_list):"""通过坐标列表得到坐标方向字符串。（第一个坐标就是一个边界点的坐标，第二个坐标是第一个经过的目标点坐标）。通过两个坐标之前的值关系获得方向。:param coordinate_list: 路径坐标列表:return: coordinate_direction_str: 坐标方向字符串（坐标是第一个坐标，也就是某个边界点坐标）。"""border_coordinate = coordinate_list[0] # 边界点坐标x1, y1 = border_coordinate[0], border_coordinate[1] # 横坐标，纵坐标first_target_coordinate = coordinate_list[1] # 第一个目标的坐标x2, y2 = first_target_coordinate[0], first_target_coordinate[1] # 横坐标， 纵坐标direction = ""if x1 == x2 and y1 - 1 == y2:direction = "A"if x1 - 1 == x2 and y1 == y2:direction = "B"if x1 == x2 and y1 + 1 == y2:direction = "C"if x1 < x2 and y1 == y2:direction = "D"if x1 - 1 == x2 and y1 - 1 == y2:direction = "E"if x1 - 1 == x2 and y1 + 1 == y2:direction = "F"if x1 + 1 == x2 and y1 + 1 == y2:direction = "G"if x1 + 1 == x2 and y1 - 1 == y2:direction = "H"return str(x1) + str(y1) + directiondef get_longest_shout_situation(n, target_location, border_location):"""得到射中目标最多的射箭情景。:param n: 矩阵的规格大小(n * n)。:param target_location: 所有目标坐标列表。:param border_location: 所有边界点坐标列表。:return:"""max_add = n - 2 # 最多假设可射中的点数# 记录走势列表step_list_list = []# 遍历边界点列表：for border_dot in border_location:# A：向左 B：向上 C：向右 D：向下 E：左上 F：右上 G：右下 H：左下# 示例：向左：A : x,y-1step_list_list = move_to_get_step_list(max_add, border_dot, target_location, step_list_list)for i in range(len(step_list_list)):print(i, ": ", step_list_list[i])max_len = 0 # 获取最长的路径for i in range(len(step_list_list)):temp_len = len(step_list_list[i])if temp_len > max_len:max_len = temp_lenprint("最长路径长度", max_len)max_len_index_list = [] # 记录最长路径的下标位置for i in range(len(step_list_list)):if len(step_list_list[i]) == max_len:max_len_index_list.append(i)print("最长路径下标", max_len_index_list)max_len_str = [] # 记录最长的坐标方向字符串for index in max_len_index_list:target_coordinate_list = step_list_list[index]print("目标：", target_coordinate_list)temp_str = get_coordinate_direction_str_by_coordinate_list(target_coordinate_list)max_len_str.append(temp_str)print(max_len_str)min_coordinate_direction_str = min(max_len_str)print(min_coordinate_direction_str)def main():# 1. 获得表格大小和目标的坐标（格式化输入的内容：表格大小和目标坐标）n, target_location = format_input()print("表格规格大小", n)print("目标点坐标", target_location)# 2. 得到边界的坐标border_location = get_border_location(n)print("边界点坐标", border_location)print("实际的边界点个数", len(border_location))print("理论上边界点个数（n*2+(n-2)*2）", n*2+(n-2)*2)# 3. 根据表格规格、目标点列表、边界点列表得到目标的射中情况get_longest_shout_situation(n, target_location, border_location)if __name__ == "__main__":main()

屏蔽了输出过程提示的：

# 箭头处在边界位置上，需要判断边界的标号def format_input():"""格式化输出的内容，将输入的字符串转换成数值（整数）:return:n:方格行列数。target_location_list：目标坐标列表。"""n = int(input("请输入：\n")) # 方格大小 n * n# 目标位置target_location_str = input().split(" ") # 通过空格切分为列表# print(target_location_str) # ['13', '21', '41', '42', '44']target_location_list = [list(item) for item in target_location_str] # 将坐标字符串转换成列表# print(target_location_list_str)for i in range(len(target_location_list)): # 将字符串坐标转换成数字坐标target_location_list[i][0] = int(target_location_list[i][0])target_location_list[i][1] = int(target_location_list[i][1])# print(target_location_list)return n, target_location_listdef get_border_location(n):"""根据表格规格得到边界坐标列表。:param n: 表格规格 n * n。:return: border_location_list"""border_location_list = [] # 总的边界点个数应该是：n*2+(n-2)*2for i in range(n):# 第一行border_location_list.append([0, i])# 最后一行border_location_list.append([n-1, i])for i in range(1, n-1):# 最左侧border_location_list.append([i, 0])# 最右侧border_location_list.append([i, n-1])return border_location_listdef move_to_get_step_list(max_add, border_dot, target_location, step_list_list): # 通过移动找到目标路径(射箭后箭经过的路线)"""为了防止get_shout_situation()方法太过冗长，故写此方法，用于在get_shout_situation()方法中调用，找到所有的射箭可用路径。:param max_add: 可能的最多可以射中的目标。:param border_dot: 某一个边界点坐标。:param target_location: 目标位置列表:param step_list_list: 射中目标的路径列表:return: step_list_list：射中目标的路径列表，作为下一个get_shout_situation()方法内的循环运行的move_to_get_step_list()方法的参数"""# A：向左 B：向上 C：向右 D：向下 E：左上 F：右上 G：右下 H：左下# 1. 向左：A : x,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0], border_dot[1] - i] # x,y-1# 假定的目标if assume_target in target_location and assume_target not in temp_step: # 判断假定目标是否在目标列表中, 并且假定目标是否在当前的路线中temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1: # 当发射箭头到达第一个目标之前经过的空格就跳过continueelse:break# 2. 向上：B : x-1,ytemp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1]] # x-1,yif assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 3. 向左：C : x,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0], border_dot[1] + i] # x,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 4. 向下：D : x+1,ytemp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1]] # x+1,yif assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 5. 向左上：E : x-1,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1] - i] # x-1,y-1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 6. 向右上：F : x-1,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] - i, border_dot[1] + i] # x-1,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 7. 向右下：G : x+1,y+1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1] + i] # x+1,y+1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:break# 8. 向左下：H : x+1,y-1temp_step = [border_dot]for i in range(1, max_add+1):assume_target = [border_dot[0] + i, border_dot[1] - i] # x+1,y-1if assume_target in target_location and assume_target not in temp_step:temp_step.append(assume_target)if temp_step not in step_list_list:step_list_list.append(temp_step)elif assume_target not in target_location and len(temp_step) == 1:continueelse:breakreturn step_list_listdef get_coordinate_direction_str_by_coordinate_list(coordinate_list):"""通过坐标列表得到坐标方向字符串。（第一个坐标就是一个边界点的坐标，第二个坐标是第一个经过的目标点坐标）。通过两个坐标之前的值关系获得方向。:param coordinate_list: 路径坐标列表:return: coordinate_direction_str: 坐标方向字符串（坐标是第一个坐标，也就是某个边界点坐标）。"""border_coordinate = coordinate_list[0] # 边界点坐标x1, y1 = border_coordinate[0], border_coordinate[1] # 横坐标，纵坐标first_target_coordinate = coordinate_list[1] # 第一个目标的坐标x2, y2 = first_target_coordinate[0], first_target_coordinate[1] # 横坐标， 纵坐标direction = ""if x1 == x2 and y1 - 1 == y2:direction = "A"if x1 - 1 == x2 and y1 == y2:direction = "B"if x1 == x2 and y1 + 1 == y2:direction = "C"if x1 < x2 and y1 == y2:direction = "D"if x1 - 1 == x2 and y1 - 1 == y2:direction = "E"if x1 - 1 == x2 and y1 + 1 == y2:direction = "F"if x1 + 1 == x2 and y1 + 1 == y2:direction = "G"if x1 + 1 == x2 and y1 - 1 == y2:direction = "H"return str(x1) + str(y1) + directiondef get_longest_shout_situation(n, target_location, border_location):"""得到射中目标最多的射箭情景。:param n: 矩阵的规格大小(n * n)。:param target_location: 所有目标坐标列表。:param border_location: 所有边界点坐标列表。:return:"""max_add = n - 2 # 最多假设可射中的点数# 记录走势列表step_list_list = []# 遍历边界点列表：for border_dot in border_location:# A：向左 B：向上 C：向右 D：向下 E：左上 F：右上 G：右下 H：左下# 示例：向左：A : x,y-1step_list_list = move_to_get_step_list(max_add, border_dot, target_location, step_list_list)# for i in range(len(step_list_list)):# print(i, ": ", step_list_list[i])max_len = 0 # 获取最长的路径for i in range(len(step_list_list)):temp_len = len(step_list_list[i])if temp_len > max_len:max_len = temp_len# print("最长路径长度", max_len)max_len_index_list = [] # 记录最长路径的下标位置for i in range(len(step_list_list)):if len(step_list_list[i]) == max_len:max_len_index_list.append(i)# print("最长路径下标", max_len_index_list)max_len_str = [] # 记录最长的坐标方向字符串for index in max_len_index_list:target_coordinate_list = step_list_list[index]# print("目标：", target_coordinate_list)temp_str = get_coordinate_direction_str_by_coordinate_list(target_coordinate_list)max_len_str.append(temp_str)# print(max_len_str)min_coordinate_direction_str = min(max_len_str)print(min_coordinate_direction_str)def main():# 1. 获得表格大小和目标的坐标（格式化输入的内容：表格大小和目标坐标）n, target_location = format_input()# print("表格规格大小", n)# print("目标点坐标", target_location)# 2. 得到边界的坐标border_location = get_border_location(n)# print("边界点坐标", border_location)# print("实际的边界点个数", len(border_location))# print("理论上边界点个数（n*2+(n-2)*2）", n*2+(n-2)*2)# 3. 根据表格规格、目标点列表、边界点列表得到目标的射中情况get_longest_shout_situation(n, target_location, border_location)if __name__ == "__main__":main()

运行结果