信息工程学院算法分析实践环节习题集--2016年
序号 项目名称 搜索图中最小控制顶点集合 任务描述 设计要求 指导教师 人数 1 1． 给定一个无向连通子图G=(V, E)，其中V表示图中顶点集合，E表示边的集合。G的最小控制顶点集合为V的一个子集，S；假设集合R表示V排除集合S后剩余顶点集合，即,= V； 则最小控制顶点集合S满足约束条件: R中任意一个顶点至少与S的一个顶点直接相连。 例如下图中红色顶点集合MDset表示一个最小控制顶点集合，任意一个绿色的顶点至少与一个红色顶点直接相连。 读取文件(网络)，设计算法求解刘全中 最小控制顶点集合。文件中数据格式如下： A B B C C D B D 每一行表示图的两个顶点，且两个顶点之间有一条边。算法： Input：图文件 Output:最小控制顶点集合 2． 求解最大的双边聚类的子矩阵 给定一个n行m列的矩阵E，单元格中数值1或者0，例如下图12行12列的矩阵中，灰色单元格表示1，白色单元格表示0。矩阵中一个双边聚类子矩阵(G, C), ,，满足以下条件： (1) 矩阵(G, C)的每个单元格中值都为1 (2) 不存在另一个子矩阵(G‟, C‟), ,, 满足下面两个条件： (a) (G‟, C‟)中的每一个单元格值都为1 (b) 例如：下图左边的矩阵中其中2个双边聚类矩阵分别为({1,3},{1,3})， ({1,8},{2,3,4}) 算法输入： 存放矩阵的文件，例如图所示的文件为： 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 刘全中 1 输出所有的双边聚类矩阵 3． 图聚类的贪心算法实现 一个子图G = (v, E)的内聚性定义如下： ，其中表示子图G中边的权重之和， 表示子图G与周围顶点连接边的权重之和。注：如果图是无权图，边的权重设置为1. 例如：如下图中，假设子图G表示包含A, B, D,E四个顶点， G = ({A, B, D, E})，则， = 5. 则f(G) = 10/(10+5). 如果一个子图G满足内聚性最大时，即局部最优时，则这个子图G就是一个聚类。寻找内聚行最大的子图，用贪心算法，分以下三个步骤： (1) 对于G的每一个直接邻居顶点 (外围的直接邻居)，例如G={A,B,D,E}，则G的直接邻居顶点为C, F, G. 找到具有最大值的顶点,如果,则}. (2) 对于G的每一个内部顶点，找到具有最大值的,其中表示集合G排除顶点 后的集合；，则. 算法输入： 存放图的文件，例如图的文件格式如下： A B B C C D B D 每一行表示图的两个顶点，且两个顶点之间有一条边. 算法： (3)重复步骤1和2，直到集合G不发生变化，即收敛，算法结束。 Input:图文件 Output:图中所有的内聚性最大的cluster. 4． 最大匹配率算法设计与实现 两个图A和B之间的匹配率计算公式： ，其中|A|表示图A中顶点个数，表示图A和图B共同顶点组成的子图。例如下图中R1和P1的匹配率为：(4*4)/(4*5) = 0.8 . 给定两组子图R, P, 例如，如下图R = {R1, R2}，P={P1, P2, P3}, 图中的边上的权值表示两个图之间的匹配率。R和P之间最大匹配率计算方法如下： 1. 找出一组边，使得P和R中的每一个顶点最多出现一条边上，而且边的权重累加和最大。 2. 最大匹配率为：第1步选择边的权重之和除以R中子图的个数 例如: 下图中最大匹配率为：(0.8+0.75)/2 Input： 两组图 Output：输出最大匹配率 两个图文件格式如下： A B C D E F G H I 每一行表示一个子图 5． 图合并算法的设计与实现 给定若干个子图，如果两个子图的重复度大于等于0.8，需要合并这两个子图。两个子图A和B重复度计算公式为：, 例如：X={A, B, C, D, E}, Y = {B, C, D,E},则 = (4*4)/(4*5) = 0.8，则子图x和y需要合并。 合并算法有两种方法: 方法一、从文件逐行扫描每一个子图，如果后面的子图于前面的子图重复度超过0.8，则把这两个子图合并为一个新的子图。 方法二、把每一个子图抽象为一个顶点，如果两个子图的重复度超过0.8,则把对应的两个顶点连一条边，这样构造一个新的图。然后从新的图中搜索连通子图，每一个连通子图中所有的顶点进行合并。 Input: 子图文件，文件的格式如下： A B C D E F G H I 每一行表示一个子图 Output，合并后的子图，输出到一个新的文件中。 要求： 用两种方法分别实现，并比较两种方法的时间复杂度 6． 简单数据集跳跃显露模式挖掘算法设计与实现 跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生次数大于等于一个支持度计数阈值的模式。 例如下表中数据，假定2。那么在类别为D1上的跳跃显露模式有：{b,e}，{c,d,e} 利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。 刘全中 1 7． 简单数据集频繁关闭模式挖掘算法设计与实现 频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设2。频繁模式：{a}，{b}，{c}, …….., {a,c,f,m}等 利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有的频繁关闭 刘全中 1 对于模式p，如果不存在模式p',pp'. 使得包含p的事物和包含p'的事物相同。那么p就是一个关闭频繁模式。 例如，假设2，{a,c,f,m}就是一个关闭频繁模式。 8． 工作分配问题 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算法， 为每一个人都分配1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。 刘全中 1 9． 无分隔符字典问题 设 (1,2,...,k)是n个互不相同的符号组成的符号集。Lk{1,2,...,k|i,1ik}是中字符组成的长度为k的字符串全体。 SLk是Lk的1个无分隔符字典是指对任意a1,a2...akS和b1,b2...bkS，则 设计一个算法，对于给定的正整数n和k,编程计算Lk的最大无分隔符字典 数据输入：有文件input.txt给出输入数据。文件第1行有2个正整数n和k 结果输出： 刘全中 1 {a2a3...akb1,a3a4...b1b2,...,akb1b2..bk-1S} 无分隔符字典问题要求对给定的n和以及正整数k,编程计算Lk的最大无分隔符字典。 将计算出的Lk的最大无分隔符字典的元素个数输出到文件output.txt. 输入文件示例： 2 2 输出： 2. 10． 最少个数运算符求解算法的设计与实现 关于整数的二元运算#定义为 (X # Y) = 十进制整数X的各位数字之和 * 十进制整数Y的最大数字+Y的最小数字 例如，(9 # 30)=9*3+0=27. 对于给定的十进制X和K,由X和#运算可以组成各种不同的表达式.试设计一个算法，计算由X和#运算组成的值为k的表达式最少需要用多少个#预算。 设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最小的路径) 输入：各城市间的旅费表有输入文件提供 输出：旅费最少的一条路径及总费用。 利用Java实现所要求的算法，开发一个GUI界面，接受两个数据X和K, 然后在界面上输出需要#的个数。 刘全中 1 11． 放行路线选择算法的设计与实现 利用Java, C实现所要求的算法。 时间充分，设计一个图形化界面，读入文件后把N个城市的带权(花费)显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上 刘全中 1 12． N色方柱问题 设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置方案。 编程任务： 对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一种叠置方案，使得柱体的4个侧面的每一侧均有n中不同的颜色。 数据输入： 由文件input.txt给出输入数据。第1行有1个正整数n，0=0为实数。对任意给定的整数k和图中两个顶点s和t， k- 边最短路径定义为：一条从s到t的路径，路径上的边数不超过k，且路径上所有边的权值之和最小。 52． 假定某国家发行了n种不同面值的邮票，并规定每个信封上最多只允许贴m张邮票。对给定的n和m的值，现要求一个信封上所贴邮票的邮资可以是某个区间[1,maxpostage]的每个值，即所谓连续邮资。 设计一个回溯法算法求使maxpostage最大的邮资面值组合。 例如：n=5 和m=4时 面值为(1,3,11,15,32)的5种邮票， 可形成[1,70]的最大连续邮资区间。 详细论述见下题 王湘桃 1 53． 54． 序列模式挖掘 序列模式挖掘 请用类Apriori算法或它的扩展算法GSP算法求解下面序列模式挖掘问题。 毛锐 毛锐 1 1 请用FreeSpan算法或它的扩展算法Prefixspan算法求解下面序列模式挖掘问题。 序列模式挖掘在web页访问模式，顾客购买习惯已经DNA序列分析等方面应用非常广泛，涉及的主要概念如下： 假设代表一个项目集合，即项集（Itemset）。事物数据库D是由元祖｛（sid,sequence）｝构成的集合，包含sid字段和sequence字段，可以表示为D=,事务(i=1,2,…,n)等于项目集的某个非空子集。如果有是I的子集，事物数据库中项目集 的支持度可以通过计算包含的事物数与D中包含的序列数的比值得到，支持度的计算公式如下： Support( 针对事物数据库D和项目集I,I的非空子集的支持度大于或者等于用户给定的最小支持度（minsup）,该子集称为频繁项目集。在频繁项目集中，最大的频繁项是指不被其他任何频繁项集所包含的项集。 如果项集，其中代表一个项，其中 1≤k≤m, S=>代表一个序列，其中为序列的元素，并且1。序列中的每个元素都包含的不同的项目。在序列中，元素element可以表示成。序列的长度可以定义为在序列中所包含有的项的个数，l-序列代表长度为l的序列。如果有两个序列，序列 α=<,序列 β=<,假设有一系列整数，并且满足条件时，那么序列α为序列β的子序列，表示为 αβ。在事务数据库S中，包含序列α 的事务序列的个数称之为序列α 的支持数，可以表示为 Support(α)。在事务数据库中，把满足用户指定的最小支持度阈值 minsup 的序列模式称之为频繁序列模式， k-模式代表序列模式的长度等于 k。 对于用户给出的事务数据库 S 以及最小支持度 minsup，序列模式挖掘的任务就是找出事务数据库中所有支持度大于或者等于 minsup 的序列模式或者最大频繁序列模式。 问题描述： 下表记录了5个顾客在一个月内的购买行为，为方便处理，按顾客号和时间进行了排序。 转换成序列数据库如下表： 假设用户指定的最小支持度minsup=30%,计算满足minsup 要求的最大频繁序列模式。 参考输出：<(I1)(I2,I5)>和<(I1)(I6)> 55． 跳蚤问题 Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一 个高空钢丝的正。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有MN张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N<=15,M<=100000000)。 毛锐 1 Output 可以完成任务的卡片数。 Sample Input 2 5 Sample Output 这24张卡片分别是： (1,1,5),(1,2,5),(1,3,5),(1,4,5),(1,5,5), (2,1,5),(2,2,5),(2,3,5),(2,4,5),(2,5,5), (3,1,5),(3,2,5),(3,3,5),(3,4,5),(3,5,5), (4,1,5),(4,2,5),(4,3,5),(4,4,5),(4,5,5), (5,1,5),(5,2,5),(5,3,5),(5,4,5) 56． 旅游预算 一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则： 若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站； 每次加油时都加满； 在一个加油站加油时，司机要花费2元买东西吃； 司机不必为其他意外情况而准备额外的油； 汽车开出时在起点加满油箱；计算精确到分（1元=100分）。 编写程序估计实际行驶在某路线所需的最小费用。 从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况： 第一行为起点到终点的距离（实数） 毛锐 1 第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。 输出格式： 答案输出到当前目录下的文本文件“route.out”中。 该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。 测试数据： route.dat 500 30 25.4 10 20 102.0 0.999 130.0 1.000 144.1 1.111 150.2 1.100 166.5 1.050 180.0 1.142 188.0 1.205 190.1 1.300 220.0 1.329 234.1 1.299 244.2 1.123 256.3 1.479 275.0 1.029 277.6 1.129 299.0 1.022 320.0 1.002 360.0 2.000 381.8 1.009 421.4 1.562 470.3 2.100 route1.dat 475.6 11.9 27.4 14.98 6 102.0 0.999 220.0 1.329 256.3 1.479 275.0 1.029 277.6 1.129 381.8 1.009 参考输出 route.out 10.00 0 route1.out 27.31 1 57． 猫和老鼠 猫Tom和鼠Jerry同住在一矩阵地窖中。猫要吃鼠，鼠要吃奶酪。地窖中有2种地砖：有洞砖与无洞砖。一个洞足以让鼠钻入，但猫不能。以图形界面的形式完成以下任务： 随机地生成一个地窖，并给猫、鼠和奶酪安排一个位置。如： fffffffffffffff fppppppppppppCf fhfffffffffffpf fpppmhppppppppf fpffffffpffffff fppppppppppTppf fffffffffffffff 其中c表示猫，m表示鼠，h表示洞，f表示不能通行 毛锐 1 （2） 鼠先行，猫后行。两者皆满足以下规定： 1）必须上、下、左或右移动 2）鼠必须走1步（穿过p或h） 3）猫必须走1或2步（穿过p） （3） 当鼠吃到奶酪或猫抓到鼠时，游戏结束。 58． 父子打牌 问题描述： 一对父子喜欢打牌，他们想出了一种玩法。假设他们分别有 n 张牌，每张牌有一个战力 值，他们知道自己和对手每张牌的战力。两人进行 n 次较量，每次较量双方各出一张牌，每 张牌限比一次。儿子通过某种手段已经预先打探到了父亲的出牌顺序。 比赛规则：任意一方出的牌的战力值高于另一方，则出的牌战力值高的一方获胜。其中 胜者可以从对方手中得到￥200，输者必须给对方￥200。如果双方出的牌的战力值相同，则 为平局，平局各不付钱。 问儿子要使用怎样的出牌策略，才能使自己赚的钱最多（或者输的钱最少）。 编程任务： 对于给定的儿子和父亲的n张牌的战力，输出进行n场比赛后，求儿子最多可以赚到的钱。 数据输入： 输入数据的第一行为一个整数 n，表示儿子和父亲拥有的牌的数量。第二行的 n 个整数， 表示儿子拥有的牌的战力值。第三行的 n 个整数，表示父亲拥有的牌的战力值。输入数据有 多组，当 n＝0 时，表示输入数据结束。（0 <= n <= 1000） 结果输出: 将计算出的儿子最多可以赚到的钱输出。 输入示例 3 93 84 72 96 88 75 2 毛锐 1 21 21 21 21 2 25 24 27 23 0 输出示例 200 0 0 59． 魔法花园 问题描述：哈利被困在了一个魔法花园里。魔法花园是一个 N*M 的矩形，在其中有着许 多植物， 这些植物会在时刻 T 消失，如果 T 是 K的倍数。哈利每单位时间都会选择上、下、左、右四 个方向的其中一个进行移动。 实验任务：已知哈利的位置和出口的位置，哈利希望你能告诉他最少需要多少时间能离开魔法花 园，如果无法移动或无法找到出口，哈利会使用移形幻影。 数据输入 ：第一行有一个正整数 T(1<=T<=10)，表示样例数。 每个样例数据的第一行有三个正整数 N、M 和 K（1<=N,M<=100,2<=K<=10），表示魔法花 园是 N 行 M 列的。 接下来的 N 行每行有 M 个字符，„0‟代表空的地板，“1”代表障碍，“2”代表哈利 的起始位置，“3”代表出口的位置。 数据输出：输出一个数，表示哈利离开魔法花园最少需要的时间，如果无法离开则输出 毛锐 1 “Mobiliarbus”。 60． Needleman-Wunsch算法 全局序列比对 尝试找到两个完整的序列 S1 和 S2 之间的最佳比对。如S1=GCCCTAGCG S2=GCGCAATG 如果设定每个匹配字符为1分，每个空格为-2分，每个不匹配为-1分，则下面的比对就是全局最优比对：S1'=GCCCTAGCG S2'=GCGC_AATG,连字符“_”代表 毛锐 1 空格。在 S2' 中有五个匹配字符，一个空格（或者反过来说，在 S1' 中有一个插入项），有三个不匹配字符。这样得到的分数是 (5×1) + (1×-2) + (3×-1) = 0，这是能够实现的最佳结果。 请用Needleman-Wunsch 算法实现上面全局序列比对的最优结果，算法描述如下： 该算法用来计算全局比对。它的思路与 LCS 算法相似。这个算法也使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。而且也能通过以下三个途径到达每个单元格：1.来自上面的单元格，代表将左侧的字符与空格比对。2.来自左侧的单元格，代表将上面的字符与空格比对。3.来自左上侧的单元格，代表与左侧和上面的字符比对（可能匹配也可能不匹配）。该单元格的值来自于以下3个中的最大值：（1）上方的值-2 （2）左边的值-2 （3）如果该单元格所在的行于所在的列对应的字符相等，则为左上值加1，否则为左上值-1。 61． 中点画线、Bresenham画线算法 中点画线算法:假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素用Java语言，或者C++语言 点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素要求：开发出图形化界面，可点；当M在Q的上方时，则取P1为下一个象素点。Bresenham画线算法： 以指定端点画线段或者使用鼠// 假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2). 标画线。 // 根据对称性,可推导至全象限内的线段. 1.画起点(x1,y1). 2.准备画下个点。x坐标增1，判断如果达到终点，则完成。否则，由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点. 2.1.如果线段ax+by+c=0与x=x1+1的交点的y坐标大于M点的y坐标的话,下个点为U(x1+1,y1+1) 王美丽 1 2.2.否则,下个点为B(x1+1,y1) 3.画点(U或者B). 4.跳回第2步. 5.结束. 62． 简单图形的平移、旋转、缩放 判断1000小球是否碰撞？ 可以产生一些基本几何体（球，椭球体，圆锥，长方体，四面体等），大小先利用缺省值，用Java语言，或者C++语言 然后在点取物体，在菜单上选择操作方式，程序应该能自动生成变换矩阵并显示出来。另要求：开发出图形化界面。 外还可以定义变换，放入变换列表，将若干个变换组合起来形成统一的变换矩阵，然后一下实施变换操作。 四叉树是一种树状数据结构在每一个节点上会有四个子区块. 四叉树常应用于二维空间资Java或者C++ 料的分析与分类. 将资料区分成为四个象限. 资料范围可以是方形或矩形或其他任意形状， 可分解成为各自的区块 每一个区块可持续分解直到资料无法分解为止树状数据结构依造四叉树法加以区分 王美丽 1 63． 王美丽 1 如下图： ． 八叉树实现点云数据的存储 C++ 八叉树（Octree）的定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。 要求利用八叉树结构实现点云数据的存储。 王美丽 1 65． 电话号码的字符串处电话号码的字符串处理并排序输出，但是实现时有几个注意的地方 1、用map存储比较方便，可以自动根据string的排序规则排序，而且题目数据恰好是的K-V存储特点。 使用Java语言 王美丽 1 理 2、用另一个字符串重新拼接待输出地字符串比直接对输入字符串进行替换移位等操作要方便。 3、注意字符和数字的ASCII的转化。 4、‘-’的加入可以在输出的时候，输到第4个字符的时候先输出‘-’。 5、map，set，vector，deque，list等容器要熟练使用。 问题：蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 输入为多组数据，Java或者C++ 每组数据由一个正整数N组成。（N不大于100） 对于每一组数据，输出一个N行的蛇 形矩阵。两组输出之间不要额外的空行。 矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。 示例 输入：5 输出： 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 王美丽 1 66． 蛇形矩阵 67． 数字布置问题 把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续。Java或者C++ 王美丽 1 68． 甲虫走迷宫 一只甲虫在一个迷宫(一个10×10的矩阵表示)中移动，迷宫中有若干个柱子（在矩阵中表Java或者C++ 示为值为1的单元）。甲虫从迷宫中的某个位置出发，按照预先设置的指令在迷宫中行进： 指令是一串由1~4组成的数字，分别代表行进的4个方向：1代表向上，2代表向右，3代表向下，4代表向左。当按照移动指令移动后的位置是一个柱子或超出了迷宫的范围则忽略该步指令。最终程序将显示指令序列结束后的甲虫所处的位置。 宝石游戏比较有趣，它在13X6 的格子里进行。游戏给出红色、蓝色、黄色、 橘黄色、 绿色、和柴色的宝石。当任何三 个以上宝石具有相同颜色并且在一条直线（横竖斜）时，这些宝石 可以消去。游戏如图所示。现在给定当前游戏状态和一组新的石头， 请编程计算当所有石头落下时游戏的状态 输入：第一行n 表示n 组测试数据。 下面每一个测试数据包含一个13 X 6 的字符表，其中B 表示蓝色，R 表示红色，O 表王美丽 1 69． 宝石游戏 李宏利 1 示橘黄色、Y 表示黄色，G 表示绿色，P 表示紫色，W 表示此处没有宝石。接下来三行，每行包含一个字符，表示新来的宝石下落的位置。 输出： 每一个测试样例，输出当所有宝石落下后游戏的状态。 样例输入： 1 WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW BBWWWW BBWWWW OOWWWW B B Y 3 样例输出： WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW OOYWWW 70． 罗密欧与朱丽叶 罗密欧与朱丽叶身处一个m×n的迷宫中。每一个方格表示迷宫中的一个房间。这m× n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这样一条道路。 李宏利 1附录：
图7 坦克大战
