湖南省第二届“软考杯”大学生程序设计大赛试题.pdf_大学文库

湖南省第二届“软考杯”大学生程序设计大赛试题试题1人类的大脑是按功能分区的。正常人的大脑分区都是活跃的,分区之间有着广泛的神经连接而脑病患者的某些大脑分区则是不活跃的,处于“睡眠”状态。最近的研究发现:如果某个“睡眠分区X与其它至少3个活跃分区保持连接1年时间,则分区X会“苏醒”过来,恢复成活跃状态。“苏醒”后的分区不会再转入“睡眠”状态有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后,其中3个分区同时“苏醒”过来。根据上文的结论,若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来? 输入输入文件的第1行仅包含1个整数M,取值范围是3,26],它表示病人大脑的分区数第2行也只包含1个非负整数N,它表示分区之间的连接数(如果分区A与分区B相连,则分区B也与分区A相连。由于这样的连接是等价的,所以只计数1次) 第3行包含3个相邻的英文字母,分别代表刚刚同时“苏醒”的3个分区。第4行中包含N个用空格分割的字符串,每个字符串包含2个英文字母,分别代表2个相连接的分区输出如果该病人的大脑分区经过若干年后能够全部“苏醒”,请在输出文件中按格式输出一行 “ WAKE UP IN n YEARS”(其中n指分区全部“苏醒”需要的年数) 如果该病人的大脑分区无法全部“苏醒”,请在输出文件中按格式输出一行: THIS BRAIN NEVER WAKES U 示例输入: 输出: WAKE UP IN 3 YEARS AB AC AH BD BC BF CD CF CH DF FH 试题2测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数,代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型,元素为合数时对应土地上的植物为常见类型。为保护稀有植物,林业局雇佣你编写程序分析上述数值方阵,从中检测出稀有植物区和非稀有植物区。划分区域的原则是:如果数值方阵中的两个元素同为质数或同为合数,而且它们共行相邻或共列相邻,则这两个元素同属一个区域输入:输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行,同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数,代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100,元素的值不会大于10000000 输出:针对输入文件中的每一个数值方阵分别输出如下信息

湖南省第二届“软考杯”大学生程序设计大赛试题试题 1 人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠” 分区 X 与其它至少 3 个活跃分区保持连接 1 年时间，则分区 X 会“苏醒”过来，恢复成活跃状态。“苏醒”后的分区不会再转入“睡眠”状态。有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中 3 个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？输入：输入文件的第 1 行仅包含 1 个整数 M，取值范围是[3, 26]，它表示病人大脑的分区数。第 2 行也只包含 1 个非负整数 N，它表示分区之间的连接数（如果分区 A 与分区 B 相连，则分区 B 也与分区 A 相连。由于这样的连接是等价的，所以只计数 1 次）。第 3 行包含 3 个相邻的英文字母，分别代表刚刚同时“苏醒”的 3 个分区。第 4 行中包含 N 个用空格分割的字符串，每个字符串包含 2 个英文字母，分别代表 2 个相连接的分区。输出：如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行： “WAKE UP IN n YEARS” （其中 n 指分区全部“苏醒”需要的年数）如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行： “THIS BRAIN NEVER WAKES UP” 示例输入： 6 11 HAB AB AC AH BD BC BF CD CF CH DF FH 输出： WAKE UP IN 3 YEARS 试题 2 测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。输入：输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过 100，元素的值不会大于 100000000。输出：针对输入文件中的每一个数值方阵分别输出如下信息：

1该数值方阵的序号(按照其在输入文件中的位置从1计起)。格式是:“ Area n:”(n代表方阵序号) 稀有植物区域的数目和每个稀有植物区域的面积(按升序排列)。格式是: “ M unique vegetation regions:ala2…”(M为区域数目,al,a2,等代表每个区域的面积) 3非稀有植物区域的数目。格式是:“ K non-unique vegetation regions”(K为区域数目) 具体的输出格式请参考示例。示例输入: 输出: Area 1 249 2 unique vegetation regions: 2 3 17637 1 non-unique vegetation regions 29811 Area 2 4 2 non-unique vegetation regions 572133 461l17 891329 试题3某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他:“演员的出场费很高,能不能让他们一人分演多个角色?充分挖掘他们的潜力,也可以节省我们的开支嘛!”导演大呼“有创意”,并顺手把剧本塞给你,“你研究研究剧本, 最少需要几个演员”,说着就准备出门去再拉几个广告赞助商,临走前他又补充了几点要求男演员只能演男角色,女演员只能演女角色 2角色的扮演者确定下来后,在演出的过程中就不能中途更改。 3如果两个角色会同时在一个场景中出现,则这两个角色必须由两个不同的演员扮演。导演走后,你翻开剧本看了看,发现了一张场景清单,也就是本题目的输入文件。输入:输入文件的第一行包含用空格分隔的3个正整数,M,F和S。其中M代表剧中的男角色数目, 取值在[1,10之间:F代表剧中的女角色数目,取值在[,10之间;S代表剧中的场景数目,取值在[1,100 之间。第二行和第三行分别列出了男角色和女角色的名字,每个名字都是一个英文字符串,名字之间有空格分隔。下面的S行分别描述了每个场景中出现的角色数和角色名(有空格分隔)。输出:本剧需要的男女演员的最少数目,具体格式如下 “ You need x actors and y actresses”其中x和y分别代表男、女演员的最少数目示例输入输出: 436 You need 3 actors and 2 actresses

1 该数值方阵的序号（按照其在输入文件中的位置从 1 计起）。格式是：“Area n:” (n 代表方阵序号) 2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是： “M unique vegetation regions: a1 a2 ...” (M 为区域数目，a1, a2,...等代表每个区域的面积) 3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K 为区域数目) 具体的输出格式请参考示例。示例输入： 3 2 4 9 17 6 37 29 8 11 4 2 3 12 15 5 7 21 33 4 6 11 17 8 9 13 29 -1 输出： Area 1: 2 unique vegetation regions: 2 3 1 non-unique vegetation regions Area 2: 2 unique vegetation regions: 4 4 2 non-unique vegetation regions 试题 3 某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你，“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求： 1 男演员只能演男角色，女演员只能演女角色。 2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。 3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。输入：输入文件的第一行包含用空格分隔的 3 个正整数，M, F 和 S。其中 M 代表剧中的男角色数目，取值在[1, 10]之间；F 代表剧中的女角色数目，取值在[1, 10]之间；S 代表剧中的场景数目，取值在[1, 100] 之间。第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。下面的 S 行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。输出：本剧需要的男女演员的最少数目，具体格式如下： “You need x actors and y actresses” 其中 x 和 y 分别代表男、女演员的最少数目示例输入： 4 3 6 输出： You need 3 actors and 2 actresses

示例输入输出: (11,LL)(7,LLL)(8,R) 54811134721 (5,)(4,L)(13,RL)(2,LLR)(1RRR)(4,RR)O not complete (3,L)(4R)O 试题5在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎 Bangle的搜索结果不尽人意,比如你按关键词搜索“ crazy stone”本意是想搜索一个名为《 crazy stone》的电影,结果 Bangle 的10万条返回信息大部分是你不需要的。 Bangle倾向于把所有包含“ crazy”和“ stone”两个关键的网页都返回给你,而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了100个 “ crazy”,在间隔了5600个词后又出现了100个“sone”,结果这个网页被 Bangle放在搜索结果列表的第10位,而它对你来说其实没用。因此,你希望改进现有的搜索引擎,使用户能更明确地控制搜索。你的设想是:在关键词的前面添加一个距离阈值,限定关键词之间的最大允许距离。比如“0 crazy stone”表示“cray”和“ stone”两个关键词在文中必须是相邻出现的,“2 crazy stone”表示这两个关键词在文中出现的间隔不能大于2个词。标点和空格不算入间隔,关键词的出现次序也不做限制。我们称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“ The director of Crazy Stone is very young….”和“ Why to say the stone is crazy.”两段短文都是合格的。采用这种方法,用户就能更好地控制搜索精度,减少垃圾结果。你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词的个数大于2,则只需其中任意两个关键词在文中的出现距离不大于距离阈值,就认为该短文是满足搜索要求的。关键词的出现次序不做限定输入:输入文件中包含不多于50条搜索元语和不多于250段短文。每条搜索元语占据一行,以“P”开头,后面依次跟一个非负整数代表距离阈值和若干小写的字符串代表关键词,并有空格分隔。 2每段短文都以“T”开头,以“”结尾。“”只会出现在短文的末尾。每段短文的长度都不大于255个字符,可能占据多行。每行最多80个字符,短文的每个后续行开头都至少有一个空格。 3在读取短文时请忽略所有非字母字符,比如原始短文“ Dont rock- the boat as Metaphor in 1984”应该被读取为“ Dont Rock the Boat as Metaphor in”,“HP2l00X”应该被读取为“HPX”。文件的结尾行包含单独的字符“#”。输出:输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始(搜索元语的序号是指搜索元语在输入文件中出现的次序,从1开始编号),后面紧跟一个冒号及空格,然后是以升序排列的符合该搜索元语要求的短文序号,短文的序号是指短文在输入文件中出现的次序,从 1开始编号。短文的序号之间以逗号分隔,不含空格。示例输输出: 1:1,2 P: 3 concepts conceptions

示例输入： (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) () 输出： 5 4 8 11 13 4 7 2 1 not complete 试题 5 在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎 Baigle 的搜索结果不尽人意，比如你按关键词搜索“crazy stone”本意是想搜索一个名为《crazy stone》的电影，结果 Baigle 的 10 万条返回信息大部分是你不需要的。Baigle 倾向于把所有包含“crazy”和“stone”两个关键的网页都返回给你，而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了 100 个 “crazy”，在间隔了 5600 个词后又出现了 100 个“stone”，结果这个网页被 Baigle 放在搜索结果列表的第 10 位，而它对你来说其实没用。因此，你希望改进现有的搜索引擎，使用户能更明确地控制搜索。你的设想是：在关键词的前面添加一个距离阈值，限定关键词之间的最大允许距离。比如“0 crazy stone”表示“crazy”和“stone”两个关键词在文中必须是相邻出现的，“2 crazy stone”表示这两个关键词在文中出现的间隔不能大于 2 个词。标点和空格不算入间隔，关键词的出现次序也不做限制。我们称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“The director of Crazy Stone is very young....”和“Why to say the stone is crazy...”两段短文都是合格的。采用这种方法，用户就能更好地控制搜索精度，减少垃圾结果。你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词的个数大于 2，则只需其中任意两个关键词在文中的出现距离不大于距离阈值，就认为该短文是满足搜索要求的。关键词的出现次序不做限定。输入：输入文件中包含不多于 50 条搜索元语和不多于 250 段短文。 1 每条搜索元语占据一行，以“P:”开头，后面依次跟一个非负整数代表距离阈值和若干小写的字符串代表关键词，并有空格分隔。 2 每段短文都以“T:”开头，以“|”结尾。“|”只会出现在短文的末尾。每段短文的长度都不大于 255 个字符，可能占据多行。每行最多 80 个字符，短文的每个后续行开头都至少有一个空格。 3 在读取短文时请忽略所有非字母字符，比如原始短文“Don't Rock -- the Boat as Metaphor in 1984”应该被读取为“Dont Rock the Boat as Metaphor in”，“HP2100X”应该被读取为“HPX”。文件的结尾行包含单独的字符“#”。输出：输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始（搜索元语的序号是指搜索元语在输入文件中出现的次序，从 1 开始编号），后面紧跟一个冒号及空格，然后是以升序排列的符合该搜索元语要求的短文序号，短文的序号是指短文在输入文件中出现的次序，从 1 开始编号。短文的序号之间以逗号分隔，不含空格。示例输入： P: 0 rock art P: 3 concepts conceptions 输出： 1: 1,2 2:

art rock metaphor concepts 3:1,2,3,4 T: Rock Art of the Maori T: Jazz and rock- Art Brubeck and Elvis Presley T: Don't Rock ---the Boat as Metaphor in 1984, Concepts and( Mis)-Conceptions of an Art Historian. I T: Carved in Rock, The Art and Craft of making promises believable when your phone bills have gone through the roof 试题6当我们给大洋彼岸的朋友发出一封emal或给家乡的亲人发送一条手机短信时,我们一般不会担心对方收到错误的信息。然而,无论 email还是手机短信在抵达目的地前都必需化为电信号穿越无数的电缆和设备,甚至化作无形的电磁波在天空中传播,衰减和噪音时刻都威胁着你发出的信息。为了保证通信的正确性,必需及时发现传输错误并予以纠正,这是现代通信技术中的重要研究内容。般的解决思路是在原始信息的后面附加一些校验信息,通过这些校验信息来判断传输的正确性。循环冗余码CRC就是这样一种信息校验方法。它的思路是待传输的信息是由字节序列组成的,可以看作是一个很长的正二进制数B。当传输B时,在其后附上两个字节的CRC校验值组成B'。CRC校验值不是任意取的,它要使B'能被一个16位的预定义值g整除。信息的接收方也知道g,因此对方只需把接收值除以g看余数是否为零就能判断传输的正确性。在本题中我们设定g=34943(十进制)。你的任务是编写程序计算任意输入信息对应的CRC校验值。输入:输入文件中每一行的内容(不包括换行符)就代表一条待传输的信息。每一条待传输信息包含不多于1024个ASCI字符。首字符为“#”的行代表输入的结束输出:输出文件的每一行包含两个16进制数(以空格分隔)代表输入文件中对应行中待传输信息的两字节CRC校验值。每个校验值应该在十进制数的0到34942之间示例输入: 输出: this is a test 试题7按规矩客户应该在SENY公司把货物发出之后的30天之内付清货款,否则SENY公司就有遭客户赖帐的风险。为了规避风险,SENY公司与一家商业保险公司签订了协议,协议规定:保险公司为SENY的每个客户提供一定额度的支付担保,担保额度与对应客户的财政记录有关但在实际运营中,如果某客户的欠款额已经高出保险公司所能提供的担保额度,为了留住客户, SENY公司还是会继续跟该客户交易并发货。当然,此时超出保险公司担保额度以上的欠款将由SENY

P: 1 art rock metaphor concepts T: Rock Art of the Maori| T: Jazz and Rock - Art Brubeck and Elvis Presley| T: Don't Rock --- the Boat as Metaphor in 1984, Concepts and (Mis)-Conceptions of an Art Historian.| T: Carved in Rock, The Art and Craft of making promises believable when your `phone bills have gone through the roof| # 3: 1,2,3,4 试题 6 当我们给大洋彼岸的朋友发出一封 email 或给家乡的亲人发送一条手机短信时，我们一般不会担心对方收到错误的信息。然而，无论 email 还是手机短信在抵达目的地前都必需化为电信号穿越无数的电缆和设备，甚至化作无形的电磁波在天空中传播，衰减和噪音时刻都威胁着你发出的信息。为了保证通信的正确性，必需及时发现传输错误并予以纠正，这是现代通信技术中的重要研究内容。一般的解决思路是在原始信息的后面附加一些校验信息，通过这些校验信息来判断传输的正确性。循环冗余码 CRC 就是这样一种信息校验方法。它的思路是：待传输的信息是由字节序列组成的，可以看作是一个很长的正二进制数 B。当传输 B 时，在其后附上两个字节的 CRC 校验值组成 B’。CRC 校验值不是任意取的，它要使 B’能被一个 16 位的预定义值 g 整除。信息的接收方也知道 g，因此对方只需把接收值除以 g 看余数是否为零就能判断传输的正确性。在本题中我们设定 g = 34943（十进制）。你的任务是编写程序计算任意输入信息对应的 CRC 校验值。输入：输入文件中每一行的内容（不包括换行符）就代表一条待传输的信息。每一条待传输信息包含不多于 1024 个 ASCII 字符。首字符为“#”的行代表输入的结束。输出：输出文件的每一行包含两个 16 进制数（以空格分隔）代表输入文件中对应行中待传输信息的两字节 CRC 校验值。每个校验值应该在十进制数的 0 到 34942 之间。示例输入： this is a test A # 输出： 77 FD 00 00 0C 86 试题 7 按规矩客户应该在 SENY 公司把货物发出之后的 30 天之内付清货款，否则 SENY 公司就有遭客户赖帐的风险。为了规避风险，SENY 公司与一家商业保险公司签订了协议，协议规定：保险公司为 SENY 的每个客户提供一定额度的支付担保，担保额度与对应客户的财政记录有关。但在实际运营中，如果某客户的欠款额已经高出保险公司所能提供的担保额度，为了留住客户， SENY 公司还是会继续跟该客户交易并发货。当然，此时超出保险公司担保额度以上的欠款将由 SENY

输出:输出文件的每一行代表输入文件中对应数据样例中所有客户的非担保债务风险占其总债务风险的比例。该比例值的精度保留到小数点后两位,数值后面紧跟一个英文百分号示例输入: 输出: l1.85% 400003 350003261 150004572 4000097123 550004 120001052 300003264 330004473 500006294 试题8在由方格子拼成的矩形迷宫中,每次只能朝前、后、左、右(分别用N,S,WE表示)中的任一方向移动一格。每移动一格就消耗一定的能量。某些格子里有障碍物,所以不能移动到这样的格子里;还有些格子里有宝贝,每个宝贝都有其特定的拿起能量和搬运能量。拿起能量是指从格子的地板上拿起宝贝需要花费的能量,搬运能量是指拿着这个宝贝移动一格所消耗的额外能量。在迷宫里指定一个起点和一个终点,请你谋划一条行进路线,从起点出发沿路收集到所有宝贝并最终抵达终点,要求走这条路线所花费的能量是所有可能路线中最小的。输入:输入文件的第一行包含两个由空格分开的整数R和C,分别代表迷宫的行数和列数,两者都不大于20。后续的R行,每行C个字符代表了迷宫的地图。其中每个字符表示一个方格子及其属性( 表示空格子,#表示有障碍的格子,*表示有宝贝的格子,'S表示起点格子,T表示终点格子)。后一行包含一个整数,表示移动一格所花费的能量。再后面一行包含一系列的数据对,每个数据对由用空格分开的两个整数组成,分别表示对应宝贝的拿起和搬运能量。数据对的次序与宝贝在迷宫中的按列从上至下,按行从左至右的先后次序一致。迷宫中最多有10个宝贝,宝贝彼此位于不同的格子中输入数据中可能包含多个迷宫样例,每个样例都有上述结构的数据,输入文件的最后一行包含两个由空格分开的输出:针对输入文件中的每个迷宫样例,首先输出“MAP”后跟该样例的序号(从1开始记),在下行输出走最优路线所花费的能量。如果不存在这样一条路线,请输出“ NO WAY” 示例输入输出: MAPI NO WAY

输出: 输出文件的每一行代表输入文件中对应数据样例中所有客户的非担保债务风险占其总债务风险的比例。该比例值的精度保留到小数点后两位，数值后面紧跟一个英文百分号。示例输入： 1 2 40000 3 35000 32 61 15000 45 72 40000 97 123 55000 4 12000 10 52 30000 32 64 33000 44 73 50000 62 94 输出： 11.85% 试题 8 在由方格子拼成的矩形迷宫中，每次只能朝前、后、左、右（分别用 N, S, W, E 表示）中的任一方向移动一格。每移动一格就消耗一定的能量。某些格子里有障碍物，所以不能移动到这样的格子里；还有些格子里有宝贝，每个宝贝都有其特定的拿起能量和搬运能量。拿起能量是指从格子的地板上拿起宝贝需要花费的能量，搬运能量是指拿着这个宝贝移动一格所消耗的额外能量。在迷宫里指定一个起点和一个终点，请你谋划一条行进路线，从起点出发沿路收集到所有宝贝并最终抵达终点，要求走这条路线所花费的能量是所有可能路线中最小的。输入：输入文件的第一行包含两个由空格分开的整数 R 和 C，分别代表迷宫的行数和列数，两者都不大于 20。后续的 R 行，每行 C 个字符代表了迷宫的地图。其中每个字符表示一个方格子及其属性（’.’ 表示空格子，’#’表示有障碍的格子，’*’表示有宝贝的格子，’S’表示起点格子，’T’表示终点格子）。后一行包含一个整数，表示移动一格所花费的能量。再后面一行包含一系列的数据对，每个数据对由用空格分开的两个整数组成，分别表示对应宝贝的拿起和搬运能量。数据对的次序与宝贝在迷宫中的按列从上至下，按行从左至右的先后次序一致。迷宫中最多有 10 个宝贝，宝贝彼此位于不同的格子中。输入数据中可能包含多个迷宫样例，每个样例都有上述结构的数据，输入文件的最后一行包含两个由空格分开的 0。输出: 针对输入文件中的每个迷宫样例，首先输出“MAP”后跟该样例的序号（从 1 开始记），在下一行输出走最优路线所花费的能量。如果不存在这样一条路线，请输出“NO WAY” 示例输入： 5 8 #......T 输出： MAP1 NO WAY