信息学奥赛试题精选33题（附带题解）

第1~10题为基础题，第11~20题为提高题，第21~33为综合题

注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。^_^

基础题：

【1 Prime Frequency】

【问题描述】

给出一个仅包含字母和数字（0-9, A-Z 以及 a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。 输入：

输入的第一行给出一个整数T ( 0

对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按ASCII 值升序排列。如果没有字符的频率是素数，输出“empty”（没有引号）。 样例输入 3 ABCC AABBBBDDDDD ABCDFFFF 注：

试题来源：Bangladesh National Computer Programming Contest 在线测试：UVA 10789

样例输出 Case 1: C Case 2: AD Case 3: empty 提示

先离线计算出[2‥2200]的素数筛u[]。然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u[p[i]]=1且ASCLL码值为i的字符）。若没有频率为素数的字符，则输出失败信息。

【2 Twin Primes】 【问题描述】

双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul St?ckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。在本题中请你给出第S对双素数，其中S 是输入中给出的整数。 输入：

输入小于10001行，每行给出一个整数S (1≤ S≤ 100000)，表示双素数对的序列编号。输入以EOF结束。 输出：

对于输入的每一行，输出一行，给出第S对双素数。输出对的形式为(p1,空格p2)，其中“空格”是空格字符(ASCII 32)。本题设定第100000对的素数小于20000000。 样例输入 1 2 3 4 注：

试题来源：Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Bangladesh

在线测试：UVA 10394

样例输出 (3, 5) (5, 7) (11, 13) (17, 19) 提示

设双素数对序列为ans[]。其中ans[i]存储第i对双素数的较小素数（1≤i≤num）。ans[]的计算方法如下：

使用筛选法计算出[2，20000000]的素数筛u[]；

按递增顺序枚举该区间的每个整数i：若i和i+2为双素数对（u[i]&&u[i+2]）,则双素数对序列增加一个元素（ans[++num]=i）。

在离线计算出ans[]的基础上，每输入一个编号s，则代表的双素数对为(ans[s]，ans[s]+2)。

【3 Less Prime】 【问题描述】

设n为一个整数，100≤n≤10000，请找到素数x，x ≤ n，使得n-p*x最大，其中 p是整数，使得p*x≤n<(p+1)*x。 输入:

输入的第一行给出一个整数M，表示测试用例的个数。每个测试用例一行，给出一个整数N，100≤N≤10000。 输出:

对每个测试用例，输出一行，给出满足上述条件的素数。 样例输入 5 4399 614 8201 101 7048 注：

试题来源：III Local Contest in Murcia 2005 在线测试：UVA 10852

样例输出 2203 311 4111 53 3527 提示

要使得n-p*x最大（x为素数，p为整数，p*x ≤ n<(p+1)*x），则x为所有小于n的素数中，被n除后余数最大的一个素数。由此得出算法：

先离线计算出[2‥11111]的素数表su[]，表长为num。然后每输入一个整数n，则枚举小于n的所有素数，计算tmp=max{n%su[i]su[i]?n}，满足条件的素数即为对应tmp=n%

1?i?numsu[k]的素数su[k]。

【4 Prime Words】 【问题描述】

一个素数是仅有两个约数的数：其本身和数字1。例如，1, 2, 3, 5, 17, 101和10007是素数。

本题输入一个单词集合，每个单词由a-z以及A-Z的字母组成。每个字母对应一个特定的值，字母a对应1，字母b对应2，以此类推，字母z对应26；同样，字母A对应27，字母B对应28，字母Z对应52。

一个单词的字母的总和是素数，则这个单词是素单词（prime word）。请编写程序，判定一个单词是否为素单词。 输入：

输入给出一个单词集合，每个单词一行，有L个字母，1≤L≤20。输入以EOF结束。 输出：

如果一个单词字母的和为素数，则输出“It is a prime word.”；否则输出“It is not a prime word.”。 样例输入 UFRN 样例输出 It is a prime word. contest AcM 注：

试题来源：UFRN-2005 Contest 1 在线测试：UVA 10924

It is not a prime word. It is not a prime word. 提示

由于字母对应数字的上限为52，而单词的长度上限为20，因此我们首先使用筛选法，离线计算出[2‥1010]的素数素数筛u[]。

然后每输入一个长度为n的单词，计算单词字母对应的数字和

X=

n,s[i]?'A'?27s[i]?{'A'..'Z'} ? s[i]?'a'?1s[i]?{'a'..'z'} i?1若x为[2‥1010]中的一个素数（u[x]=1），则表明该单词为素单词；否则该单词非素单词。

【5 Sum of Different Primes】 【问题描述】

一个正整数可以以一种或多种方式表示为不同素数的总和。给出两个正整数n和k，请您计算将n 表示为k个不同的素数的和会有几种形式。如果是相同的素数集，则被认为是相同的。例如8可以被表示为3 + 5和5 + 3，但不区分。

如果n和k分别为24和3，答案为2，因为有两个总和为24的集合 {2, 3, 19}和{2, 5, 17} ，但不存在其他的总和为24的3个素数的集合。如果n = 24，k = 2，答案是3，因为存在3个集合{5, 19}, {7, 17}以及{11, 13}。如果n = 2，k = 1，答案是1，因为只有一个集合{2} ，其总和为2。如果n = 1，k = 1，答案是0，因为1不是素数，不能将{1}计入。如果n = 4，k = 2，答案是0，因为不存在两个不同素数的集合，总和为4。

请您编写一个程序，对给出的n和k，输出答案。 输入：

输入由一系列的测试用例组成，最后以一个空格分开的两个0结束。每个测试用例一行，给出以一个空格分开的两个正整数n和k。本题设定n ≤ 1120，k ≤ 14。 输出：

输出由若干行组成，每行对应一个测试用例，一个输出行给出一个非负整数，表示对相应输入中给出的n和k有多少答案。本题设定答案小于231。 样例输入 24 3 24 2 2 1 样例输出 2 3 1 1 1 4 2 18 3 17 1 17 3 17 4 100 5 1000 10 1120 14 0 0 注：

试题来源：ACM Japan 2006

0 0 2 1 0 1 55 200102899 2079324314 在线测试：POJ 3132，ZOJ 2822，UVA 3619

提示

设

su[]为[2..1200]的素数表；f[i][j]为j拆分成i个素数和的方案数(1≤i≤14, su[i]≤j≤1199)。显然，边界值f[0][0]=1。

首先，采用筛选法计算素数表su[]，表长为num。然后每输入一对n和k，使用动态规划方法计算k个不同素数的和为n的方案总数：

枚举su[]表中的每个素数su[i](1≤i≤num） 按递减顺序枚举素数个数j(j=14‥1)：

按递减顺序枚举前j个素数的和p（p=1199‥su[i]）:

累计su[i]作为第j个素数的方案总数f[j][p]+=f[j-1][p-su[i]];

最后得出的f[k][n]即为问题解。 【6 Common Permutation】

【问题描述】

给出两个小写字母的字符串，a和b，输出最长的小写字母字符串x使得存在x的一个排列，是a的子序列，同时也存在x的一个排列是b的子序列。 输入：

输入有若干行。连续的两行组成一个测试用例，也就是说，第1和第2行构成一个测试用例，第3和第4行构成一个测试用例，等等。每个测试用例的第一行是字符串a，第二行是字符串b。每个字符串一行，至多由1000个小写字母组成。 输出：

对每个测试用例，输出一行，给出x。如果有若干个x满足上述要求，选择按字母序列第一个。

样例输入 pretty women walking down the street 样例输出 e nw et 注：

试题来源：World Finals Warm-up Contest, University of Alberta Local Contest 在线测试：UVA 10252

提示

试题要求按递增顺序输出两串公共字符的排列。计算方法如下： 设S1=a1a2…ala，S2= b1b2…blb。

先分别统计S1中各字母的频率c1[i]和S2中各字母的频率c2[i]（1≤i≤26,其中字母‘a’对应数字1, 字母‘b’对应数字2,…，字母‘z’对应数字26）。

然后计算S1和S2的公共字符的排列：递增枚举i(1≤i≤26)，若i对应的字母在S1和S2中同时存在（（c1[i]≠0）&&（c2[i]≠0））,则字母'a'+i在排列中出现k=min{c1[i]，c2[i]}次。

【7 Anagram】

【问题描述】

给出一个字母的集合，请您编写一个程序，产生从这个集合能构成的所有可能的单词。 例如：给出单词\，您的程序产生这三个字母的所有不同的组合——输出单词\

\和\。

程序从输入中获取一个单词，其中的一些字母会出现一次以上。对一个给出的单词，程序产生相同的单词只能一次，而且这些单词按字母升序排列。 输入：

输入给出若干单词。第一行给出单词数，然后每行给出一个单词。一个单词是由A到Z的大写或小写字母组成。大写字母和小写字母被认为是不同的，每个单词的长度小于13。 输出：

对输入中的每个单词，输出这个单词的字母产生的所有不同的单词。输出的单词按字母升序排列。大写字母排在相应的小写字母前，即'A'<'a'<'B'<'b'<...<'Z'<'z'。 样例输入 3 aAb abc acba 样例输出 Aab Aba aAb abA bAa baA abc acb bac bca cab cba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa 注： 试题来源：ACM Southwestern European Regional Contest 1995 在线测试：POJ 1256，UVA 195

提示

建立字母与整数间的对应关系：

字母‘a’对应0，字母‘A’对应1;…；字母‘z’对应50，字母‘Z’对应51。 为了按照字母升序的要求生成单词的所有排列，首先将单词的所有字母转化为数字，然后递增排序数串，排列中每个位置的数字按由左而右顺序从数串中选择。

设单词长度为l，数串的第i个位置已访问标志为v1[i]，初始时v1[]清零；数字k对应的字母已使用标志为v2[k]，v2[]为递归程序内的局部变量（0≤i≤l-1，0≤k≤51）。 生成所有排列的计算过程为一个递归子程序：

void dfs(int d){ //从当前位置d出发，递归计算单词的所有排列 if (d==l) 输出当前数字排列对应的单词； //生成单词的一个排列 }else{ v2[]清零; //所有字母未确定 for(int i=0;i

} } } }

显然，主程序设数串的所有位置未访问（v1[]清零），递归调用dfs(0)，便可按字母升序要求输出单词的所有排列。

【8 How Many Points of Intersection?】

【问题描述】

给出两行，在第一行有a个点，在第二行有b个点。我们用直线将第一行的每个点与第二行的每个点相连接。这些点以这样的方式排列，使得这些线段之间相交的数量最大。为此，不允许两条以上的线段在一个点上相交。在第一行和第二行中的相交点不被计入，在两行之间允许两条以上的线段相交。给出a和b的值，请计算P(a, b)，在两行之间相交的数量。例如，在下图中a = 2，b = 3，该图表示P(2, 3) = 3。

输入：

输入的每行给出两个整数a ( 0

对输入的每一行，输出一行，给出序列编号，然后给出P(a, b)的值。本题设定输出值在64位有符号整数范围内。 样例输入 2 2 2 3 3 3 0 0 样例输出 Case 1: 1 Case 2: 3 Case 3: 9 注：

试题来源：Bangladesh National Computer Programming Contest, 2004 在线测试：UVA 10790

提示

如3线交于一点，则一定可以通过左右移动一个点使其交点分开，上面线段上的两点与

下面线段上的两点可以产生一个交点。按照乘法原理，p(a，b)=错误！未找到引用源。。 【9 Stripies】

【问题描述】

生化学家发明了一种很有用途的生物体，叫 stripies ，（实际上，最早的俄罗斯名叫 polosatiki ，不过科学家为了申请国际专利时方便不得不起了另一个英文名）。stripies 是透明，无定型的，群居在一些象果子冻那样的有营养的环境里。在大部分时间stripies是在移动中，当两条stripies碰撞时，这两条stripies就融合产生一条新的stripies。经过长时间的观察，科学家们发现当两条stripies碰撞融合在一起时，新的stripies的重量并不等于碰撞前两条stripies 的重量。不久又发现两条重量为m1和m2的stripies 碰撞融合在一起，其重量变为2*sqrt(m1*m2)。科学家很希望知道有什么办法可以限制一群stripies 的总重量的减少。 请您编写程序来解决这个问题。本题设定3条或更多的stripies 从来不会碰撞在一起。 输入：

第一行给出N (1 ≤ N ≤ 100)，表示群落中stripies 的数量。后面的N行每行为一条stripie 的重量，范围为1-1000。 输出：

输出stripies群落可能的最小总重量。 精确到小数点后3位。 样例输入 3 72 30 50 注：

试题来源：ACM Northeastern Europe 2001, Northern Subregion 在线测试：POJ 1862，ZOJ 1543，Ural 1161

样例输出 120.00 提示

设群落中n条stripies的重量为m1m2‥mn。经过n-1次碰撞后的总重量为

1W=2((m1m2)n?12n?1m312n?2?m)

12n显然，m1m2‥mn按照重量递减的顺序排列，得出的总重量w是最小的。

【10 The Product of Digits】

【问题描述】

请您寻找一个最小的正整数Q，Q的各个位置上的数字乘积等于N。 输入：

输入给出一个整数N (0 ≤ N ≤ 109)。 输出：

输出一个整数Q，如果这个数不存在，则输出?1。 样例输入 10 注：

试题来源：USU Local Contest 1999 在线测试：Ural 1014

样例输出 25 提示

分解N的因子的度量标准：尽量分解出大因子。 注意，有两个特例： N=0时,Q=0； N=1时,Q=1；

否则采取贪心策略，按从9到2的顺序分解n的因子：先试将n分解出尽量多的因子9，再试分解出尽量多的因子8?。若最终分解后的结果不为1，则无解；否则因子由小到大组成最小的正整数Q。

提高题：

【11 Democracy in Danger】

【问题描述】

在Caribbean 盆地中的一个国家，所有的决策是由在公民大会上简单的多数投票被通过的。当地的一个政党，希望权力尽可能地合法，要求改革选举制度。他们主要论点是，岛上的居民最近增加了，它不再轻易举行公民大会。

改革的方式如下：投票者被分成K个组（不一定相等），在每个组中对每个问题进行投票，而且，如果一个组半数以上的成员投“赞成”票，那么这个组就被认为投“赞成”票，否则这个组就被认为投“反对”票。如果超过半数的组投“赞成”票，决议就被通过。 开始岛上的居民高兴地接受了这一做法，然而，引入这一做法的党派，可以影响投票组的构成。因此，他们就有机会对不是多数赞同的决策施加影响。

例如，有3个投票组，人数分别是有5人，5人和7人，那么，对于一个政党，只要在第一组和第二组各有3人支持就足够了，有6个人赞成，而不是9个人赞成，决议就能通过。 请您编写程序，根据给出的组数和每组的人数，计算通过决议至少需要多少人赞成。 输入：

第一行给出K，表示组数（K≤101）；第二行给出K个数，分别是每一组的人数。K以及每组的人数都是奇数。总人数不会超过9999人。 输出：

支持某个党派对决策产生影响至少需要的人数。 样例输入 3 5 7 5 注：

试题来源：Autumn School Contest 2000 在线测试：Ural 1025

样例输出 6 提示

把每组人数从小到大排序，总共n组，则需要有??+1组同意，即人数最少的前??+1

22组。对于一个人数为k的组需要同意，则需要有

?n????n????k?+1人同意。 ???2?由此得出贪心策略：人数最少的前??+1组中，每组取半数刚过的人数。 2

【12 Box of Bricks】

?n???【问题描述】

小Bob喜欢玩方块砖，他把砖一块放在另一块的上面堆砌起来，堆成不同高度的栈。“看，我建了一面墙”，他告诉他的姐姐Alice。“不，你要让所有的栈有相同的高度，这样你就建了一面真正的墙了。” Alice反驳说。Bob考虑了一下，认为他姐姐是对的。因此他开始重新一块接一块地重新安排砖块，让所有的栈有着相同的高度。但由于Bob很懒惰，他要移动砖块的数量最少。你能帮助他吗？

输入：

输入由若干组测试用例组成。每组测试用例的第一行给出整数n，表示Bob建的栈的数目。下一行给出n个数字，表示n个栈的高度hi，本题 设定1 ≤ n ≤ 50，并且1 ≤ hi ≤ 100。

砖块的总数除以栈的数目是可除尽的。也就是说，重新安排砖块使得所有的栈有相同的高度是可以的。

输入由n = 0作为结束，程序对此不必处理。 输出：

对每个测试用例，首先如样例输出所示，输出测试用例编号。然后输出一行\minimum number of moves is k.\，其中k是移动砖块使得所有的栈高度相同的最小数。在每个测试用例后输出一个空行。 样例输入 6 5 2 4 1 7 5 0 注：

试题来源：ACM Southwestern European Regional Contest 1997 在线测试：POJ 1477，ZOJ 1251，UVA 591

样例输出 Set #1 The minimum number of moves is 5. 提示

设平均值avg=

?hi?1nin，avg即为移动后栈的相同高度。

第i个栈中砖头被移动的度量标准：若hi>avg，则栈中有hi-avg块砖头被移动。 贪心使用这个度量标准是正确的，因为砖头被移动至高度低于avg的栈中。由于砖块总数除以栈的数目是可除尽的，因此这些栈中的砖头是不须再移动的。由此得出最少移动的砖数ans=

n?(hi?1i?avghi?avg)

【13 Minimal coverage】

【问题描述】

给出直线的若干条线段，直线是X轴，线段的坐标为[Li, Ri]。求最少要用多少条线段可以覆盖区间[0, m]。 输入：

输入的第一行给出测试用例的数目，后面给出一个空行。

每个测试用例首先给出一个整数M(1≤M≤5000)，接下来若干行，每行以\Li Ri\Li|, |Ri|≤50000, i≤100000)表示线段。每个测试用例以“0 0”为结束。

两个测试用例之间用一个空行分开。 输出：

对每个测试用例，输出的第一行是一个数字，表示覆盖区间[0, m]的最少线段数。接下来若干行表示选择的线段，给出线段的坐标，按左端(Li)排序。程序不处理\。若无解，即[0, m]不可能被给出的线段覆盖，则输出\（没有引号）。 在两个连续的测试用例之间输出一个空行。 样例输入 2 1 -1 0 -5 -3 2 5 0 0 1 -1 0 0 1 0 0 注：

试题来源：USU Internal Contest March'2004 在线测试：UVA 10020，Ural 1303

样例输出 0 1 0 1 提示

把所有线段按左端点为第一关键字、右端点为第2关键字递增排序（（Li≤Li+1||(( Li == Li+1)&&( Ri< Ri+1))，1≤i≤线段数-1）。

选取覆盖线段的度量标准：在所有左端点被覆盖线段中找右端点最远的线段。 贪心实现的过程：

设当前线段覆盖到的位置为now； 所有左端点被覆盖的线段中可以覆盖最远的位置为 len，该线段为k。初始时ans=now=len=0。

依次分析序列中的每条线段：

if (Li≤now)&&（len< Ri）{ len= Ri；k=i;}

if (Li+1 >now) &&（now

if (now≥m)输出覆盖线段并退出程序；

分析了所有线段后now

【14 Annoying painting tool】

【问题描述】

你想知道一个恼人的绘画工具是什么吗？首先，本题所讲的绘画工具仅支持黑色和白色，因此，图片是一个像素组成的矩形区域，像素不是黑色就是白色。其次，只有一个操作改变像素的颜色：

选择一个r行c列的像素组成的矩形，这个矩形是完全在一个图片内。作为操作的一个结果，在矩形内的每个像素会改变其颜色（从黑到白，从白到黑）。

最初，所有的像素是白色的。创建一个图片，应用上述的操作数次。你能描绘出你心目的那幅图片吗？ 输入：

输入包含若干测试用例。每个测试用例的第一行给出4个整数n，m，r和c，（1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100），然后的n行每行给出您要画的图的一行像素。第i行由m个字符组成，描述在结束绘画时第i行的像素值('0'表示白色，'1'表示黑色)。 最后一个测试用例后的一行给出4个0。 输出：

对每个测试用例，输出产生最终绘画结果需要操作的最小数；如果不可能，输出-1。 样例输入 3 3 1 1 010 101 010 4 3 2 1 011 110 011 110 3 4 2 2 0110 0111 0000 0 0 0 0 注：

试题来源：Ulm Local 2007 在线测试：POJ 3363

样例输出 4 6 -1 提示

进行一次操作的度量标准：当前子矩阵左上角的像素和目标矩阵的对应像素的颜色不

同。贪心实现的方法如下

由左而右、自上而下枚举子矩阵的左上角a[i][j] (1≤i≤n-r+1，1≤j≤m-c+1)： 若左上角像素的颜色与目标矩阵对应元素的颜色不同（a[i][j]!=b[i][j]），则操作次数c+1；子矩阵内所有像素的颜色取反（a[k][l]^=1，i≤k≤i+k-1，j≤l≤j+c-1）。 最后再检验一遍当前矩阵a[][]和目标矩阵b[][]是否完全一样。若还有不一样的地方，则说明无解；否则c为产生最终绘画结果需要操作的最少次数。

【15 Troublemakers】

【问题描述】

每所学校都有麻烦制造者（troublemaker） —— 那些孩子们可以使教师的生活苦不堪言。一个麻烦制造者还是可以管理的，但是当你把若干对麻烦制造者放在同一个房间里，教学就变得非常困难。在Shaida夫人的数学课上有n个孩子，其中有m对麻烦制造者。情况变得如此的差，使得Shaida夫人决定将一个班级分成两个班级。请您帮Shaida夫人将麻烦制造者的对数减少至少一半。 输入：

输入的第一行给出测试用例数N，然后给出N个测试用例。每个测试用例的第一行给出n (0≤n≤100)和m (0

对于每个测试用例，先输出一行\x:\，后面给出L ——要转到另一间房间的孩子的数目，下一行列出那些孩子。在两个房间中麻烦制造者对数的总数至多是m/2。如果不可能，则输出\代替L，然后输出一个空行。 样例输入 2 4 3 1 2 2 3 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 样例输出 Case #1: 3 1 3 4 Case #2: 2 1 2

注：

试题来源：Abednego's Graph Lovers' Contest, 2006 在线测试：UVA 10982

提示

以孩子为节点，每对麻烦制造者之间连边，构造无向图g。设两个班级分别对应集合s[0]和集合s[1]，其中s[1]中的人数较少。

依次确定每个孩子i（1≤i≤n）所在的班级：将孩子1‥孩子i-1中与孩子i结对制造麻烦的孩子划分成s[0]和s[1]集合。若s[1]中的孩子数较少，则孩子i送入s[1]集合，这就是孩子i转移到另一间房间的度量标准。贪心实现的方法是 依次搜索每个节点i（1≤i≤n）：

统计节点1‥i-1中与节点i有边相连的点在集合s[0]和集合s[1]的点数； 若s[1]中的点数较少，则节点i送入s[1]集合； 最后s[1]集合中的节点对应要转到另一间房间的孩子。

【16 Constructing BST】

【问题描述】

BST（Binary Search Tree，二叉搜索树）是一个用于搜索的有效的数据结构。在一个BST中，所有左子树中的元素小于根，右子树中的元素大于根。

我们通常通过连续地插入元素来构造BST，而插入元素的顺序对于树的结构有很大的影响。请看下例：

在本题中，我们要给出从1到N的整数来构造BST，使得树的高度至多为H。BST的高度定义如下：

1. 没有结点的BST的高度为0；

2. 否则，BST的高度等于左子树和右子树的高度的最大值加1。

可以存在若干顺序可以满足这一要求。在这种情况下，取小数字排在前的序列。例如，对于N=4，H=3，我们给出的序列是1 3 2 4，而不是2 1 4 3或3 2 1 4。 输入：

每个测试用例给出两个正整数N（1≤N≤10000）和H（1≤H≤30）。输入以N=0，H=0结束，这一情况不用处理。至多有30个测试用例。 输出：

对于每个测试用例，输出一行，以“Case #: “开始，其中?#?是测试用例的编号；然后在这一行中给出N个整数的序列，在一行的结束没有多余的空格。如果无法构造这样的树，则输出“Impossible.”（没有引号）。 样例输入 4 3 4 1 6 3 0 0 注：

试题来源：ACM ICPC World Finals Warmup 1，2005 在线测试：UVA 10821

样例输出 Case 1: 1 3 2 4 Case 2: Impossible. Case 3: 3 1 2 5 4 6 提示

试题要求输出BST的前序遍历，即第一个输出根。因为要求字典序最小，所以要让根尽量小。

对于把编号为1到n的节点排成一个高度不高于h的bst，左右子树的节点数不应超过2-1。根节点的度量标准是

若根的右侧可以放满节点，则根的编号root为n-(2-1)；否则根的编号root为1，即根编号root=max{1，n-(2-1)}。

之后问题就转化成了把编号为1到root-1的节点排成一个高度不高于h-1的左bst子树和把编号为root+1到n的节点排成一个高度不高于h-1的右bst子树。

上述贪心解法是递归定义的，可递归解决。

【17 Ordering Tasks】

h-1

h-1

h-1

John有n项任务要做。不幸的是，这些任务并不是独立的，有的任务只有在其他一些任务完成以后才能开始做。 输入：

输入由几个测试用例组成。每个用例的第一行给出两个整数：1≤n≤100和m。n是任务的数量 (从1到n编号)，m 是在两个任务之间直接优先关系的数量。然后是m行，每行两个整数i和j，表示任务i必须在任务j之前执行。以实例n=m=0结束输入。 输出：

对每个测试用例，输出一行，给出n个整数，表示任务执行的一个可能的顺序。

样例输入 5 4 1 2 2 3 1 3 1 5 0 0 注：

试题来源：GWCF Contest 2 （Golden Wedding Contest Festival） 在线测试：UVA 10305

提示

样例输出 1 4 2 5 3 任务作为节点，两个任务之间的直接优先关系作为边：若任务i必须在任务j之前执行，则对应有向边，这样可将任务间的先后关系转化为一张有向图，使得任务执行的一个可能的顺序对应这张有向图的拓扑排序。设

节点的入度序列为ind[]，其中节点i的入度为ind[i](0≤i≤n-1)；

邻接表为lis[]，其中节点i的所有出边的另一端点存储在lis[i]中，lis[i]为一个List容器

队列q存储当前入度为0的节点，队首指针为h，队尾指针为t；

我们在输入信息的同时构建邻接表lis[]，计算节点的入度序列为ind[]，并将所有入度为0的节点送入队列q；

然后依次处理q队列中每个入度为0的节点： 取出队首节点x；

lis[x]容器中每个相邻节点的入度-1，相当于删除x的所有出边； 新增入度为0的节点入q队列；

依次类推，直至队列空为止。相继出队的节点q[0]‥q[n-1] 即为一个拓扑序列。

【18 Spreadsheet】

在1979年，Dan Bricklin和Bob Frankston编写了第一个电子制表应用软件VisiCalc，这一软件获得了巨大的成功，并且在那时成为Apple II计算机的重要应用软件。现在电子制表是大多数计算机的重要的应用软件。

电子制表的思想非常简单，但非常实用。一个电子制表由一个表格组成，每个项不是一

个数字就是一个公式。一个公式可以基于其他项的值计算一个表达式。文本和图形也可以加入用于表示。

请编写一个非常简单的电子制表应用程序，输入若干份表格，表格的每一个项或者是数字（仅为整数），或者是支持求和的公式。在计算了所有公式的值以后，程序输出结果表格，所有的公式都已经被它们的值代替。 输入：

输入文件第一行给出测试用例中的表格的数目。每个表格的第一行给出用一个空格分开的两个整数，表示表格的列数和行数，然后给出表格，每行表示表格的一行，每行由该行的项组成，每个项用一个空格分开。

一个项或者是一个数字值，或者是一个公式。一个公式由一个等号开始(=)，后面是一个或多个用加号(+)分开的项的名称，这样公式的值是在相应的项中的所有值的总和。这些项也可以是一个公式，在公式中没有空格。

可以设定在这些项之间没有循环依赖，因此每个表格可以是完全可计算的。

每一个项的名字是由1到3个字母（按列），后面跟着数字从1到999（按行）组成。按列的字母构成如下序列：A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, ..., BZ, CA, ..., ZZ, AAA, AAB, ..., AAZ, ABA, ..., ABZ, ACA, ..., ZZZ。这些字母相应于从1到18278的数字，如图所示，左上角的项取名为A1。

左上方的项的命名

图

输出：

除了表格的数目以及列和行的数目不重复以外，程序输出和输入的格式一样。而且，所有的公式要被它们的值取代。

样例输入 1 4 3 10 34 37 =A1+B1+C1 40 17 34 =A2+B2+C2 =A1+A2 =B1+B2 =C1+C2 =D1+D2 注：

试题来源：1995 ACM Southwestern European Regional Contest 在线测试：POJ 1420，UVA 196

样例输出 10 34 37 81 40 17 34 91 50 51 71 172 提示

在表达式中各项的命名格式，字母A?ZZZ代表列，数字1?999代表行。需要将列字母转化为列序号，行数串转化为行序号。转化方法：

A代表1，?Z代表26，字母序列ck‥c1对应一个26进制的列序号y=

?(ci?1ki ?64)*26i?1；

数串bp‥b1应一个十进制的行序号x=

?(bi?1pi?48)*10i?1。

即表达式中的项ck‥c1 bp‥b1对应表格位置（x，y）。 设

数值表格为w[][]；

表达式项所在位置值为d，（i,j）对应位置值d=j*1000+i，即d % 1000为行号，

?d?为列号。 ???1000? 我们将表格转化为一个有向图：每项为一个节点，数值项与表达式项间的关联关系为有向边。若数值项（x,y）对应表达式项（i,j）中的某项，则（x,y）连一条有向边至（i,j）。设

相邻矩阵为g，其中g[x][y]存储与数值项（x,y）关联的所有表达式项的位置值； 表达式项的入度序列为ind，即（i,j）中的表达式目前含ind[i][j]个未知项。显然ind[i][j]==0，表明（i,j）为数值项； ①构造有向图

我们边输入表格边构造有向图：若（i,j）为数值项，则数值存入w[i][j]；若（i,j）为表达式项，则取出其中的每一项，计算其对应的行号x和列号y，（i,j）的位置值送入g[x][y]邻接表，并累计（i,j）的入度（++ind[i][j]）。 ②使用删边法计算有向图的拓扑序列

首先将图中所有入度为0的节点（数值项）的位置值送入队列q；然后依次按下述方法处理队列中的每一项：

取出队首节点的位置值，将之转化为（x,y）。依次取g[x][y]中与数值项（x,y）相关联的每个表达式项的位置值，转化为表格位置（tx,ty）, 将（x,y）的值计入（tx,ty）中的表达式项（w[tx][ty]+=w[x][y]），（tx,ty）的入度-1（--ind[tx][ty]）。若入度减至0，则（tx,ty）的位置值送入q队列。

依次类推，直至队列空为止。最后输出数值表格w。

【19 Genealogical Tree】

火星人直系亲属关系的系统非常混乱。火星人在不同的群体中群居生活，因此一个火星人可以有一个父母，甚至也可以有十个父母；而且一个火星人有100个孩子也不会让人感到

输入:

输入的第一行给出整数N （2≤N≤1000），表示图G中的节点数。第二行给出指令数Q (1≤Q≤20000)。后面的Q行每行给出一条指令，有三类指令：

I u v: 插入边 (u, v)，并保证在执行这一指令时，在节点u和v之间没有边。 D u v: 删除已有的边 (u, v)，并保证在执行这一指令时，在节点u和v之间存在边。 Q u v: 查询指令，在节点u和v之间是否连通。 节点的编号从1到N。 输出:

对每条查询指令输出一行。如果两个节点是连通的，输出“Y”；否则输出“N”。

样例输入 3 7 Q 1 2 I 1 2 I 2 3 Q 1 3 D 1 2 Q 1 3 Q 1 1 注：

试题来源：POJ Monthly--2006.06.25, Zheng Zhao 在线测试：POJ 2838

提示

样例输出 N Y N Y 由于无向图是动态生成的，因此该图的存储结构采用邻接表为宜。我们按照下述方法依次处理每条命令：

若为插边指令I x y：y插入x的邻接表，x的邻接表长+1；x插入y的邻接表，y的邻接表长+1；

若为删边指令D x y：在x的邻接表中搜索y,用表尾节点覆盖该位置，x的邻接表长度-1；在y的邻接表中搜索x,用表尾节点覆盖该位置，y的邻接表长度-1；

若为查询指令Q x y：若x==y，则x和y之间连通；否则从x出发，通过BFS搜索计算x的所有可达节点。若y为可达节点，则节点x和y之间连通；否则不连通。

【32 The Net】

现在考虑Internet上一个感兴趣的问题：快速的信息传送已经成为必须。信息传送工作由位于网络节点上的路由器实现。每个路由器有它自己的一个路由器列表，给出它可以直接到达的路由器（也被称为“传输表”）。很明显，信息传送要求经过的路由器最少（也被称为

“跳数”）。

对于给出的网络，要求程序发现从信息源头到目标节点的最佳路线（最少跳数）。 输入:

第一行给出网络中路由器的个数（n）。后面的n行给出网络的描述。每行给出路由器ID，然后是一个连字符以及用逗号分开的、可以直接到达的路由器的ID列表，这一列表按升序排列。下一行给出信息传送要走的路线数目（m），后面连续的m行给出用一个空格分开的路线的起始路由器和终点路由器。输入数据包含了多个网络的描述。 输出:

对输入中给出的每个网络，先输出一行5个连字符；然后对每条路线，输出信息从起始路由器传送到目的路由器要经过的路由器列表。如果不可能进行信息传送（起始路由器和目的路由器不连通），输出字符串“connection impossible”。如果存在多条有相同“跳数”的路线，输出低ID的路线(由路由器1到2的路线是1 3 2 和1 4 2，则输出1 3 2)。

数据范围设定为：网络中路由器的数目不超过300，并且至少有2个路由器。每个路由器最多和50个路由器直接相连。

样例输入 6 1-2,3,4 2-1,3 3-1,2,5,6 4-1,5 5-3,4,6 6-3,5 6 1 6 1 5 2 4 2 5 3 6 2 1 10 1-2 2- 3-4 4-8 5-1 6-2 7-3,9 ----- 1 3 6 1 3 5 2 1 4 2 3 5 3 6 2 1 ----- 9 7 3 4 8 10 connection impossible 9 6 2 样例输出 8-10 9-5,6,7 10-8 3 9 10 5 9 9 2 注： 试题来源： 在线测试：UVA 627

提示

将路由器看作节点，则试题给出的路由器列表实际上是图的邻接表。我们可以使用flyed算法计算任意节点对之间的最短路矩阵dist[][]（最短路矩阵中元素的初始值为∞）。

计算“跳线”实际上就是计算指定节点对x和y间的一条最短路。有了最短路矩阵dist[][]，计算便变得十分容易：

若dist[x][y]为初始值∞，则x路由器和y由器不连通；否则x路由器和y由器连通。我们可按照下述方法计算和输出低ID的信息传送路线。

输出路线上的首节点x；

while (dist[x][y] != 1) //若y非最短路的尾节点

for (int k=1; k≤N; k++) //按照ID递增的顺序搜索最短路上x的相邻节点k

if (dist[x][k]==1 && dist[x][k]+dist[k][y]== dist[x][y]) { 输出节点k；

x=k; //继续找最短路上k的相邻节点 break; }

输出最短路上的尾节点y；

【33 The Warehouse】

特工007找到了疯狂的科学家Dr. Matroid的秘密武器仓库。仓库里放满了大箱子（可能致命武器就在箱子内）。在对仓库进行检查的时候，007意外地触发了警报系统。仓库有一种针对入侵者的非常有效的保护：如果触发警报，那么地板上就充满了致命的酸。因此，007可以逃脱的唯一的办法是爬到箱子上面，并达到在顶部的出口。出口是一个在天花板上的洞，如果007可以爬上通过这个洞，他便可以使用停在屋顶上的直升机逃脱。在洞的下方，有一个梯子和一个箱子，因此，目标就是到达这个箱子。

仓库的地板可视为n?n单元格的一个网格，每个单元格的大小为1米×1米。每个单元格或者是完全被一个箱子占用或没有放东西。每个箱子是长方体：占据地面的大小为1米×

1米，高度可以是2米，3米，或者4米。在图（a）中，可以看到一个仓库的实例，数字表示箱子的高度，E表示出口，圆表示特工007目前在该箱子的顶部。

图

007可以做两件事：

如果他正站在一个箱子的顶部，并在相邻的单元格中还有另外一个箱子，那么他可以移动到另一个箱子的顶部。例如，在图（a）所示的情况中，他可以向北部或向东移动，但不能向西或向南移动。请注意，只允许这四个方向的移动，对角线方向移动是不允许的。两个盒子之间的高度差并不重要。

007能够做的第二件事情是他能够向4个方向推倒他所站的箱子。用一个例子来表示推倒箱子的情况： 007的情况如图（b）所示，他可以向西推翻箱子（如图（c）所示），或向北推倒箱子（如图（d）所示）。如果箱子的高度为H，向北（或向西，向南，等等）推倒箱子，则箱子在向北（或者向西，向南，等等）方向上占据连续的H个单元格。箱子原来占据的位置将被空置（但还可以推翻另外的箱子，重新占据这个位置）。如果在箱子倒下的位置上没有被其他箱子占据，箱子才可以朝这个方向被推倒，例如，在（a）中，007所站的箱子不能朝任何一个方向被推倒。

推倒了一个箱子后，007可以朝推倒箱子的方向上跳一步跳到被推倒的箱子上（见图（c）（d）项）。如果一个箱子被推倒了，那么它不可能被再一次推倒。在出口的下方有一个箱子 (在图中标记了E的单元格)，因此不可能推翻一个箱子压在这个单元格上。警报系统不久还将放出突变体的毒蝙蝠，因此007必须尽快离开仓库。请你写一个确定到达出口的最少步数的程序，以帮助007。跳上邻近的箱子，推翻一个箱子都被计算为一步。 输入：

输入包含若干个测试用例。每个测试用例的第一行给出3个整数：仓库的大小1≤n≤8；两个整数i , j ，给出了特工007的开始位置，这些整数在1到n之间，行数由i给出，列数由j给出。后面的n行描述仓库，每行给出一个n个字符组成的字符串。每个字符对应仓库的一个单元格，如果字符是`.‘，则单元格没有被占据，字符‘2’，‘3’和‘4’分别对应于高度为 2, 3 和 4的箱子。字符`E‘表示出口的位置。

输入结束用n = i = j = 0。 输出：

对每个测试用例，输出一行，给出一个整数：到达出口的最少的步数。如果不可能到达出口，则输出‘Impossible.’(没有引号)。

样例输入 5 5 3 .2..E 18 样例输出 ...2. 4.... ....4 ..2.. 0 0 0 注：

试题来源：ACM Central Europe 2005 在线测试：POJ 2946，UVA 3528

提示

显然，该题是计算出发位置至出口的最短路。由于007推倒一次箱子被视为一步，因此仓库状态对应的图是一个无权图，采用BFS搜索的方法计算这条最短路是最合时宜的。 ①?? 采用哈希技术判重

BFS搜索的难度有2个：

存储量大：由于每一步是在先前仓库状态的基础上进行的，因此需要存储所有产生过的仓库状态，这也是出题者之所以将仓库上限设为8的原因。

需要判重：若当前的仓库状态和以前计算出的仓库状态重复，则继续搜索下去势必出现死循环。我们采用哈希技术判重：

按照自上而下、有左而右顺序给每个格子位置编号

当前仓库状态的哈希函数m=

?((位置i的字符)*126i?1n*ni?1)000007。若走入空格

(x,y)，则新的仓库状态的哈希函数m’=(m+(x+126*y))% 3000007。

对哈希表中所有已计算出仓库状态的元素值置当前测试用例编号id hash[m]=hansh[m’]=?= id。若新计算出仓库状态k，查询哈希表时发现hash[k]=id，则表明仓库状态k以前曾经产生过，应重新选择新的移动方向。 ① 扩展队首节点的方法

队列Q存储目前搜索到的非空格（出发点、目标点和堆有箱子的方格），元素包括当前仓库状态Q[].p、位置值Q[].d（(x，y)的位置值为x*100+y）和步数Q[].m。

若准备第m步走入（x,y）,走前仓库状态为p，则按照下述方法进行判重、目标判断和入队操作：

Viod add( p,x, y, M) {

if ((x,y) 为出口标志 'E'){

flag = true; //返回成功标志和最少步数m

奇怪。火星人已经习惯了这样的生活方式，对于他们来说这很自然。

在行星理事会（Planetary Council）中，这样混乱的家谱系统导致了一些尴尬。这些火星人中的杰出人士去参加会议，为了在讨论中不冒犯长辈，讨论中总是辈分高的火星人优先发言，然后是辈分低的火星人发言，最后是辈分最低还没有子女的火星人发言。然而，这个秩序的维持确实不是一个简单的任务。一个火星人并不知道他所有的父母（当然也不知道他的所有的祖父母），但如果一个孙子在比他年轻的曾祖父之前发言，这就是一个重大的错误了。

请编写一个程序，对所有的成员定义一个次序，这个次序要保证理事会的每一个成员所在的位置先于他的所有后代。 输入：

标准输入的第一行只包含一个整数N，1≤N≤100，表示火星理事会（Martian Planetary Council）的成员数。理事会成员的编号从1到N。在后面给出N行，而且第i行给出第i个成员的孩子的列表。孩子的列表是孩子编号按任意次序用空格分开的一个序列。孩子的列表可以为空。列表（即使是空列表）以0结束。 输出：

标准输出仅给出一行，给出一个编号的序列，编号以空格分开。如果存在几个序列满足这一问题的条件，请输出其中任何一个。这样的序列至少存在一个。

样例输入 5 0 4 5 1 0 1 0 5 3 0 3 0 注：

试题来源：Ural State University Internal Contest October'2000 Junior Session 在线测试：Ural 1022

提示

样例输出 2 4 5 3 1 将火星人设为节点，父亲与儿子之间连一条有向边。这个有向图的拓扑序列即为所有成员的次序。

我们边输入信息边构造相邻矩阵g，并统计节点的入度序列ind（其中g[x]存储x的所有儿子，ind[x]为节点x的入度值）。

接下来，将所有入度为0的节点送入队列q 。然后依次处理队列q中的每个节点： 取队首节点x；x的每个儿子的入度-1。若减至0，则该儿子进入队列q； 依次类推，直至队列空为止。

最后输出输出拓扑序列，即q的出队顺序。

【20 Rare Order】

一个珍稀书籍的收藏家最近发现了一本用一种陌生的语言写的一本书，这种语言采用和英语一样的字母。这本书有简单的索引，但在索引中的条目的次序不同于根据英语字母表给出的字典排序的次序。这位收藏家试图通过索引来确定这个古怪的字母表的字符的次序，(即对索引条目组成的序列进行整理)，但因为任务冗长而乏味，就放弃了。

请编写程序完成这位收藏家的任务，程序输入一个按特定的序列排序的字符串集合，确定字符的序列是什么。 输入：

输入是由大写字母组成的字符串的有序列表，每行一个字符串。每个字符串最多包含20个字符。该列表的结束标志是一个单一字符?＃?的一行。并不是所有的字母都被用到，但该列表蕴涵对于被采用的那些字母存在着一个完全的次序。 输出：

输出一行大写字母，字母的排序顺序列按输入数据进行整理所给出。

样例输入 XWY ZX ZXY ZXW YWWX # 注：

试题来源：1990 ACM ICPC World Finals 在线测试：UVA 200，UVA 5139

提示

样例输出 XZYW 输入字符串的有序列表T[]（T表的长度为tot），按照下述方法将T表转化为有向图的相邻矩阵v：

每个大写字母为一个节点，节点序号为字母对应的数值（大写字母序列[A‥Z]映射为数值序列[1‥26]），T表中同一位置上不同字母代表的节点间连有向边： for (int i = 0; i < tot; i++)

for (int j = i + 1; j < tot; j++) { len = min(T[i]的串长, T[j]的串长); for (int k=0; k

if (T[i]中第k个字母 != T[j]中第k个字母) {

v[T[i]中第k个字母对应的节点序号][T[j]中第k个字母对应的节点序号]=true; break;

}

}

计算有向图的拓扑序列，拓扑序列中节点对应的字母即为字母表中字符的次序。计算方法如下

初始化：置图中所有节点未访问标志，统计节点的入度（若v[i][j]=true，则inq[i]=inq[j]=true，++ind[j]。1≤i,j≤26）；将入度为0的节点（inq[i] && ind[i]==0）送入队列q。

依次处理队列q中的节点：取出队首节点x，x的所有相邻节点i的入度减1。若减至0（v[x][i] && --ind[i] == 0），则i节点入队。

依此类推，直至队列空为止。此时出队顺序对应的字母即为字母表中字符的次序。

综合题：

【21 Pushing Boxes】

想象您正站在一个二维的迷宫中，迷宫由是正方形的方格组成，这些方格可能被岩石阻塞，也可能没有。您可以向北，南，东或西一步移到下一个方格。这些移动被称为行走（walk）。

在一个空方格中放置了一个箱子，您可以挨着箱子站着，然后按这个方向推动这个箱子，这个箱子就可以被移到一个临近的位置。这样的一个移动被称为推（push）。除了推以外，箱子不可能用其他的方法被移动，这就意味着如果您把箱子推到一个角落，您就永远不能再把它从角落中推出。

一个空格被标识为目标空格。您的任务就是通过一系列的行走和推把一个箱子推到目标方格中（如图）。因为箱子非常重，您希望推的次数最少。您能编写一个程序来给出最佳的序列吗？

图

输入：

输入文件包含若干个迷宫的描述，每个迷宫描述的第一行给出两个整数r和c (都小于等于20)，表示迷宫的行数和列数。

后面给出r行，每行有c个字符。每个字符描述迷宫的一个方格。一个塞满岩石的方格用一个‘#’表示，一个空方格用一个‘.’表示。你开始时站的位置用‘S’表示，箱子开始的位置用‘B’表示，目标方格用‘T’表示。

输入以两个为0的r和c结束。

输出：

对输入的每个迷宫，第一行输出迷宫的编号，如样例输出。然后，如果不可能把箱子推到目标方格，输出“Impossible.”；否则，输出输出推的数目最小化的序列。如果存在多于一个的这样的序列，选择总的移动（行走和推）最小的序列。如果依然存在多于一个的这样的序列，那么任何一个序列都是可以接受的。

输出序列是一个字符串，由字符N, S, E, W, n, s, e 和w组成，其中大写字母表示推，小写字母表示行走，不同的字母代表方向北（north），南（south），东（east）和西（west）。

在每个测试用例处理后输出一个空行。

样例输入 1 7 SB....T 1 7 SB..#.T 7 11 ########### #T##......# #.#.#..#### #....B....# #.######..# #.....S...# ########### 8 4 .... .##. .#.. .#.. .#.B .##S .... ###T 0 0 注：

试题来源：ACM Southwestern European Regional Programming Contest 1997

在线测试：UVA 589，ZOJ 1249，POJ 1475

提示

样例输出 Maze #1 EEEEE Maze #2 Impossible. Maze #3 eennwwWWWWeeeeeesswwwwwwwnNN Maze #4 swwwnnnnnneeesssSSS 乍看试题，很容易看出迷宫是一个无权无向图，自然会产生使用BFS算法求最短路的猜想，这个猜想确实看到了求解的大致方向。但是深入分析试题，却可以发现许多难点。例

如，移动过程需分前后两个步骤：

⑴人行走至箱子的相邻位置；

⑵推箱子至目标位置。而在推箱子的过程中，即可以沿一个方向一直推下去，也可以步行到箱子的另一个相邻位置，换一个方向推。因此需要多次使用BFS算法。 ⑴ 输入迷宫信息

?true通过输入信息计算出相邻矩阵p，其中p[i][j]=??false

⑵计算步行情况

(i,j)无障碍(i,j)有障碍( 0≤i≤

r-1，0≤j≤c-1)，并记下箱子的起始位置（xb,yb）、目标位置（xt,yt）和你的开始位置（xs,ys）。

移动过程先是从(xs,ys)出发，行走至（xb,yb）的四个相邻格中无障碍格之一，准备推箱子。

设（xb,yb）有障碍（P[xb][yb]=false），从（xs,ys）出发，通过宽度优先搜索（BFS(xs,ys)）计算出（xs,ys）与每个无障碍格(x,y)(0≤x≤r-1，0≤y≤c-1，p[i][j]=true)的可达状态

reach[x][y]=??true?false(xs,ys)可达（x,y）(xs,ys)不可达（x,y）

若（xs,ys）可达（x,y），则将每步的行走方向记入way[x][y]。显然，way[x][y]的长度即为（xs,ys）至（x,y）间的最短路径长度。

⑶通过宽度优先搜索计算推动箱子的最佳方案

设人从（xs,ys）出发沿i方向进入（x，y）的移动方向序列为ans[x][y][i]，其最少步数为move[x][y][i]。箱子由（x，y）的i方向的相邻格推入（x，y）的被推次数为push[x][y][i]。为了避免重复进入（xb,yb）的相邻格，设

push[x][y][i]=??0??箱子沿i方向推入(xb,yb)箱子未沿i方向推入(xb,yb)

一开始（xb,yb）恢复为无障碍状态（P[xb][yb]=true），队列撤空。然后枚举开始推的位置，即（xb,yb）的四个相邻格：

若i方向的相邻格在界内且由（xs,ys）可达，则（xb,yb）和i方向入队，push[xb][yb][i]=0，将way[(（xb,yb）的i方向的相邻格)]记入ans[xb][yb][i]，其长度记入move[xb][yb][i]。推前位置确定后，进入宽度优先搜索:

若队列不空，则取出队首的坐标（x,y）和方向d，直至队列空为止。 有两种推的方案：

? 沿d方向继续推下去

? 行走至箱子方向i(i≠d)的相邻格，从i方向推箱子

①?? 沿d方向继续推

若相反的3-d方向上的相邻格（x?，y?）在界内且无障碍（如图）

图

若箱子未沿d方向推入（x?，y?）((push[x?][y?]][d]==∞))，则（x?，y?）和方向d入队； 在箱子沿d方向推入（x?，y?）的被推次数=沿d方向推入（x,y）的被推次数+1(push[x?]][y?]][d]=push[x][y][d]+1)的情况下，若人从（xs,ys）出发，沿d方向进入（x?，y?）的总步数大于沿d方向进入（x,y）的总步数+1(move[x?]][y?]][d]>move[x][y][d]+1)，则最佳路径为(xs,ys)?→(x,y)→(x?，y?)（move[x?]][y?]][d]=move[x][y][d]+1）；ans[x?]][y?]][d]=ans[x][y][d]+d方向对应字符);

在箱子沿d方向推入（x?，y?）的被推次数>沿d方向推入（x,y）的被推次数+1(push[x?]][y?]][d]>push[x][y][d]+1)的情况下，则最佳路径为先沿d方向将箱子推入（x,y），再沿d方向推一次箱子（push[x?][y?]][d]=push[x][y][d]+1；move[x?]][y?]][d]=move[x][y][d]+1）；ans[x?]][y?]][d]=ans[x][y][d]+d方向对应字符); ②另换一个方向推

若沿d方向推动箱子，则人必须在箱子位置（x，y）的d方向的相邻格（x?，y?）；若改为i方向推箱子（0≤i≤3，i≠d），则必须步行到（x，y）的i方向的相邻格(x”，y”)。计算方法如下：

设（x，y）有障碍（P[x][y]=false），从（x?，y?）出发进行BFS，计算所有可达的格子，并将到达这些格子的行走方向序列记入way（BFS(x?, y?)）。恢复（x,y）的无障碍状态（P[x][y] = true） ；

搜索除d外的每个方向i（0≤i≤3，i≠d）,计算（x,y）的i方向上的相邻格(x”，y”)：

若(x”，y”)为界内的一个无障碍格，且由(x?, y?)可达，则分析

? 若箱子未沿i方向推入(x,y)（push[x][y][i] ==∞），则（x,y）和方向i进入队列； ? 在箱子沿i方向推入（x，y）的被推次数=沿d方向推入（x,y）的被推次数的情况

下(push[x][y][i]==push[x][y][d])，若人从（xs,ys）出发，进入(x”，y”)的总步数大于进入（x?，y?）的总步数+（x?，y?）走至(x”，y”) 的总步数（move[x][y][i]>move[x][y][d]+way[x”][y”]的长度）则最佳路径为(xs,ys)?→(x’,y’)→(x”，y”)（move[x][y][i]=move[x][y][d]+ way[x”][y”]的长度，ans[x][y][i]=ans[x][y][d] + way[x”][y”]; ? 在箱子沿i方向推入（x，y）的被推次数>沿d方向推入（x,y）的被推次数的情况

下(push[x][y][i]>push[x][y][d])，则最佳路径为(xs,ys)?→(x’,y’)→(x”，y”)（move[x][y][i]=move[x][y][d]+way[x”][y”]的长度，ans[x][y][i]=ans[x][y][d]+way[x”][y”]，

箱子推至(x”，y”)的被推次数推至(x’,y’)的被推次数（push[x][y][i]=push[x][y][d]）；

⑷输出结果

通过上述BFS求出了箱子由4个方向推入（xt,yt）的最少被推次数（push[xt][yt][i]）、

人从（xs，ys）出发沿4个方向进入（xt,yt）的最少步数move[xt][yt][i](0≤i≤3)。最佳方案中最后的推动方向d必须满足如下条件：

箱子沿d方向推入（xt,yt）（push[xt][yt][d]≠∞），并且满足下述两个条件之一： 箱子被推次数是最少的push[xt][yt][d]=min{push[xt,yt][i]}

0?i?3 若被推次数最少的方案有多个，则move[xt][yt][d]是最小的 计算方法如下：

d=-1; //最佳方向初始化

for (int i = 0; i < 4; i++) //枚举4个方向 if (push[XT][YT][i]!=∞ &&(d

==-1||push[XT][YT][d]>push[XT][YT][i]||(push[XT][YT][d]==push[XT][YT][i]&&move[XT][YT][d]>move[XT][YT][i])))

else

print(ans[xt][yt][d] + \ //输出输出推的数目最小化的序列 d = i;

print(\

if (d == -1) //箱子未能推入（xt,yt）

【22 Basic Wall Maze】

在这个你要解决问题中，有一个非常简单的迷宫，组成如下：

一个6*6的方格组成的正方形。

长度在1到6的3面墙，沿着方格，水平或者垂直放置，以分隔方格。 一个开始标志和一个结束标志。 迷宫形为图：

图

你要寻找从开始位置到结束位置的最短路。仅允许在邻接的方格间移动；所谓邻接就是指两个方格有一条公共边，并且它们没有被墙隔开。不允许离开正方形。

输入：

输入由若干测试用例组成。每个测试用例由5行组成：第一行给出开始位置的列和行的值；第二行给出结束位置的列和行的值；第3，4，5行给出3面墙的位置；墙的位置或者是先给出左边的位置点，再给出右边的位置点（如果是水平的墙）；或者是先给出上方位置点，然后再给出下方位置点（如果是垂直墙）。墙端点的位置是以点与正方形左边的距离后面跟点与正方形上方位置的距离给出。 输出：

3面墙可以在方格的某一点上相交，但彼此不交叉，墙的端点在方格上。而且，从开始标志到结束标志一定会有合法的路。样例输入说明上图给出的迷宫。

最后一个测试数据后跟着一行，包含了两个零。

样例输入 1 6 2 6 0 0 1 0 1 5 1 6 1 5 3 5 0 0 注：

试题来源：Ulm 2006 在线测试：POJ 2935

提示

样例输出 NEEESWW 由于墙是沿方格线的一条线段，因此不仅要将方格作为节点，而且也要将方格线也作为节点,使得迷宫扩展为12*12的矩阵。显然，方格线的坐标值为偶数，通道的坐标值为奇数（如图11.5-5）

图

墙所在的节点设访问标志visit，避免出现“翻墙而过”的情况。显然对四周的边墙

visit[0][0] = visit[1][0]?visit[12][0] =true visit[0][0] = visit[0][1]?visit[0][12] =true visit[0][12] = visit[1][12]?visit[12][12] =true visit[12][0] = visit[12][1]?visit[12][12] =true

对由方格(x1,y1)至方格(x2,y2)的垂直墙(x1==x2):

visit[2*y1][2*x1]= visit[2*y1+1][ 2*x1]=? visit[2*y2][ 2*x1]=true

对由方格(x1,y1)至方格(x2,y2)的水平墙(y1==y2):

visit[2*y1][2*x1]= visit[2*y1][ 2*x1+1]=? visit[2*y1][ 2*x2]=true

入口方格(sx, sy )对应节点的坐标为（sx*2-1,sy=sy*2-1）, 出口方格(ex,ey )对应节点的坐标为（ex*2-1,ey*2-1） 。

有了上述图，我们便可以使用宽度优先搜索计算起点至各节点的最短路的方向序列，其中队列Q存储已访问节点的坐标位置（除墙外），prev[][]存储队列中每个节点访问时的移动方向。

既然有了起点至目标节点的最短路的方向序列，我们就可以从目标节点出发，沿prev[][]

指针的指示追溯目标节点至起始节点的路径： 取出当前节点的方向数d= prev[x][y];

若x和y为奇数，则d对应的方向字符填入路径串path首部;

x-=d方向的水平增量；y-=d方向的垂直增量；

依次类推，直至（x,y）为起点坐标为止； 最后输出路径串path。

【23 Firetruck】

中央城消防部门与交通部门协作，一起维护反映城市街道当前状况的地图。在某一天，一些街道由于修补或施工而被封闭。消防队员需要能够选择从消防站到火警地点的不经过被封闭街道的路线。

中央城被划分为互不重叠的消防区域，每个区域设有一个消防站。当火警发生时，中央调度向火警地点所在的消防站发出警报，并向该消防站提供一个从消防站到火警地点的可能路线的列表。请您编写一个程序，中央调度可以使用这个程序产生从区域的消防站到火警地点的路线。 输入：

城市的每个消防区域有一个独立的地图，每张地图的街区用小于21的正整数标识，消防站总是在编号为1的街区。输入给出若干测试用例，每个测试用例表示在不同的区域发生的不同的火警。

测试用例的第一行给出一个整数，表示离火警最近的街区的编号。

后面的若干行每行由空格分开的正整数对组成，表示未封闭街道连接的相邻的街区。（例如，如果在一行给出一对数4 7，那么在街区4和7之间的街道未被封闭，且在街区4和7的路段上没有其他街区）。

每个测试用例的最后一行由一对0组成。 输出：

对于每个测试用例，在输出中用数字来标识（CASE #1，CASE #2，等等），在一行中输出一条路线，按路线中出现的顺序，依次输出街区；输出还要给出从消防站到火警地点的所有路线的总数，其中只包括那些不经过重复街区的路线（由于显而易见的理由，消防部门不希望他们的车子兜圈子。）

不同的测试用例在不同的行上输出。

在样例输入和样例输出中，给出了两个测试用例。

样例输入 6 1 2 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0 4 2 3 3 4 5 1 1 6 7 8 8 9 2 5 5 7 3 1 1 8 4 6 6 9 0 0 注：

试题来源：1991 ACM World Finals 在线测试：UVA 208，UVA 5147

提示

样例输出 CASE 1: 1 2 3 4 6 1 2 3 5 6 1 2 4 3 5 6 1 2 4 6 1 3 2 4 6 1 3 4 6 1 3 5 6 There are 7 routes from the firestation to streetcorner 6. CASE 2: 1 3 2 5 7 8 9 6 4 1 3 4 1 5 2 3 4 1 5 7 8 9 6 4 1 6 4 1 6 9 8 7 5 2 3 4 1 8 7 5 2 3 4 1 8 9 6 4 There are 8 routes from the firestation to streetcorner 4. 我们将街区作为节点，未封闭街道连接的相邻街区间连边，构造一个无向图。路线的起点为节点1（即消防站所在的街区1），终点为离火警最近的街区编号en。试题要求计算这样的路线有多少条以及所有的路线方案。

显然可以用回溯法计算所有可能的路线。但需要注意的是，在扩展路线时，新节点y不仅要满足与路线尾节点x相邻和未访问的约束条件，还要满足y是否与终点en连通的约束条件，否则消防车无法途径y到达火警地点。为了提高搜索效率，我们可以预先通过计算

试题来源：ACM South Central USA 2006 在线测试：POJ 3083，ZOJ 2787，UVA 3631

提示

样例输出 37 5 5 17 17 9 试题的难度是怎样计算游客沿左面墙或者右面墙一直走下去的路线。设方向1‥方向4（如图）

图

方向t逆时针转90后的方向为t1=(t+3)%4，顺时针转90后的方向为t2=(t+1)%4。 我们设计一个递归函数dfs_left(x, y, t)，从游客沿t方向走入（x,y）的状态出发，计算沿左面墙走至出口的步数step：

dfs_left(x, y, t){

若(x,y)为边墙(x,y在界外)或内墙（(x,y)为?#?），则返回2； 步数step +1；

若(x,y)为出口，则返回1； 成功标志flag初始化为0；

计算t逆时针转90后的方向 tt=(t+3)%4; for (int i=0;i<3;i++){ //tt顺时针转904次

计算dfs_left(x?, y?, tt)的返回值r((x?, y?)为（x, y）的tt方向的相邻格)； 若找到出口 (r==1)，则设成功标志（flag=1）并退出for循环；

否则，若找不到出口(r==0)，则步数step +1；tt再顺时针转90(tt=(tt+1)%4） }

返回成功标志flag; }

同样，可以采用类似方法计算游客沿右面墙走至出口的步数step（递归函数dfs_right (x, y, t)），只不过是将t逆时针旋转90改为顺时针旋转90，将tt顺时针旋转90改为逆时针旋转90。

至于计算游客行走的最短路则比较简单。设

d[x][y]为游客从入口走至(x,y)的最短路长，简称(x,y)的距离值；

递归函数dfs( x, y, k)，从游客第k步走至（x,y）的状态出发，计算最短路长step： dfs( x, y, k){

若(x,y) 为边墙或内墙，或者其距离值不大于k(k≥d[x][y]），则退出程序； 设定(x,y)的距离值d[x][y] =k；

若(x,y)为出口，则设定最短路长step为k并退出程序 枚举(x,y)四个方向的相邻格(x?，y?)，递归dfs(x?，y?，k+1) }

在主程序中，我们对入口（xs，ys）的四个相邻格中非边墙或内墙的方块分别执行一次dfs_left(xs,ys, t)，即可统计出人靠左行走经过的方块数；用同样的方法亦可统计出人靠右行走经过的方块数；至于计算人走最短路经过的方块数，只要执行一次dfs (xs,ys,1) 即可。

【27 Curling 2.0】

。

。

。

。

。

。

。。

。

在行星MM-21，在他们今年的奥运会之后，冰壶（冰上溜石游戏）变得非常流行，但

他们的规则和我们的有些不同，这一游戏是在一个用正方形方格划分的冰棋盘上进行。他们只用一块石头。这一游戏的目标是将石头从开始位置用最少的移动次数移到目标位置。

如图给出了一个游戏的实例。一些正方形方格被阻塞了，存在两个特别的方格，即开始位置和目标位置，这两个方格不会被阻塞。（这两个方格不会在同一位置）一旦石头开始移动，它就会一直向前，直到它撞上一块阻塞物。为了使石头移到目标位置，在石头停止在阻塞物前的时候，你要再次推动它。

实例(S: 开始位置, G: 目标位置)

图

石头的移动遵循以下规则： 在开始的时候，石头在开始位置。

石头的移动受限于X轴，Y轴方向，禁止沿对角线移动。

当石头停滞的时候，你可以推动它让它移动。只要它没有没阻塞，你可以向任何方向推动它（如图（a））。

一旦推动了石头，石头就向前走同样的方向，直到出现下列情况之一： 石头遇上了阻塞（如图（b），（c））。 石头停在阻塞方块前。 阻塞物消失。 石头走出了棋盘。 游戏结束，失败。 石头到达到了目标方格。 石头停止那里，游戏成功结束。

在游戏中，你不能推动石头10倍次以上。如果在10次以内石头没有到达目标位置，游戏结束，失败。

石头移动 图

根据这一规则，我们想知道是否在开始位置的石头可以到达到目标位置，如果可以到达，

就要给出最低的推动次数。

实例如图1所示，将石头从开始位置移动到目标位置要推动石头4次，石头运动的路线如图（a）所示。请注意当石头到达目标位置的时候，棋盘图结构变化如图（b）所示。

石头运动的路线 棋盘图结构变化

输入：

输入是一个数据集合的序列，在输入结束是包含用空格分开的两个零的一行。数据集合的数目从未超过100。

每个数据集合的格式如下：

冰棋盘的宽度和高度h 冰棋盘的第1行 ...

冰棋盘的第h行

冰棋盘的宽度和高度满足: 2≤w≤20，1≤ ?≤20。

每行包含w个用空格分开的十进制数。这一数字描述相应的方块的状态。

0 空方块 1 阻塞 2 开始位置 3 目标位置 图1的数据集合如下：

6 6 1 0 0 2 1 0 1 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1

输出：

对于每个数据集合，打印一行，给出一个十进制整数，表示从开始位置到目标位置的路线的移动的最少次数。如果没有这样的路线，输出-1。除了这个数字，输出行没有其他的任何字符。

样例输入 样例输出 2 1 3 2 6 6 1 0 0 2 1 0 1 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 6 1 1 1 2 1 1 3 6 1 1 0 2 1 1 3 12 1 2 0 1 1 1 1 1 1 1 1 1 3 13 1 2 0 1 1 1 1 1 1 1 1 1 1 3 0 0 注：

试题来源：Japan 2006 Domestic 在线测试：POJ 3009

提示

1 4 -1 4 10 -1 设ans为从开始位置到目标位置的最少移动次数，初始值为11。我们通过递归函数dfs( x, y, k)计算ans，其中参数的意义是第k步行至（x，y）。计算过程如下： dfs( x, y, k){

若移动次数不小于上限或者最少移动次数(k>=10|| k>=ans)，则退出程序 枚举（x，y）的4个方向上的相邻格（x?，y?）：

{ 若（x?，y?）为非同行或非同列上的阻塞，则去除；从（x?，y?）递归下去（dfs(x?,y?,k+1)）;恢复递归前相邻格的阻塞状态;

否则若（x?，y?）为目标位置，则更新答案（ans=min{ans，k+1}）并退出程序 } }

我们从开始位置（xs，ys）出发，递归调用dfs(xs，ys ，0)。若得出的ans仍为初始值11，则说明无解；否则ans即为最少移动次数。

【28 Shredding Company】

您为碎纸机公司负责开发一种新的碎纸机。一台“一般”的碎纸机仅仅将纸张切成小碎片，使得其内容不可读，而这种新的碎纸机需要有以下不同寻常的基本特性。

1， 你的碎纸机要以一个目标数作为输入，并在要粉碎的那一张纸上写有一个数字。 2， 你的碎纸机将纸张粉碎（或切割）成碎片，每张碎片上都有这个数字的一位或若干

位。

3， 每张碎片上数字的总和要尽可能地接近目标数，但不能超过目标数。

例如，假设目标数为50，而纸张上数字为12346。碎纸机将纸张切碎成四张，第一张碎片上是1，第二张上是2，第三张上是34，第四张是6。它们的总和是43（= 1+ 2+ 34+ 6），是所有可能的组合中最接近目标数50但不超过50（如图）。例如，组合1，23，4和6则不成立，因为这个组合的总和是34（=1 +23 +4+ 6），小于上一个组合的总和43。组合12，34和6也不成立，因为52 (= 12 + 34 + 6)大于目标数50。

图

此外，还有3条特定的规则：

1. 如果目标数和纸张上的数字相同，则这张纸就不要粉碎。例如，如果目标数是100，而

纸张上的数字也是100，则纸张不会被粉碎。

2. 如果任何组合的总和不可能小于或等于目标数，则输出“error”。例如，如果目标数是1，

而在纸张上的数字是123，那么不可能存在可以成立的组合，因为具有最小和的组合是1，2和3，它们的和是6，大于目标数，所以要输出“error”。

3. 如果有多于一个总和最接近但没有超过目标数的组合，输出“rejected”。例如，如果目

标数是15，在纸张上的数字是111，则有两个最高是12的组合：(a) 1和11，(b)11和1；所以输出“rejected”。为了开发这样的碎纸机，请您编写一个小程序来模拟上述的特性和规则。给出两个数，第一个数是目标数，第二个数是写在要被粉碎的纸张上的数，程序要计算出碎纸机如何“切割”第二个数。 输入:

输入由若干测试用例组成，每个测试用例一行，形式如下： t1 num1 t2 num2 ...

tn numn 0 0

每个测试用例由两个正整数组成，用一个空格分开：（1）第一个整数（上面标识为ti）是目标数；（2）第二个整数（上面标识为numi）是要粉碎的纸张上的数字。

两个数不能将0作为第一位，例如123可以，但0123则不可以。可以设定两个整数长度最多6位。以一行中给出两个0作为输入结束。 输出:

对于输入中的每个测试用例，相应输出为下述3种类型之一： ? sum part1 part2 ... ? rejected ? error

在第一种类型中，partj和sum的含义如下：

1. 每个partj是一个在一张碎纸片上的一个数。partj的次序相应于在纸张上原来的数字的次

序。

2. sum是纸张被粉碎后数字和，即，sum=part1+part2+... 。

每个数字用一个空格分开。

如果不可能产生组合，输出“error”。如果存在一个以上的组合，输出“rejected”。 在每行的开始和结束，没有其他的字符，包括空格。

样例输入 50 12346 376 144139 927438 927438 18 3312 9 3142 25 1299 111 33333 103 862150 6 1104 0 0 注：

试题来源：ACM Japan 2002 Kanazawa 在线测试：POJ 1416，ZOJ 1694，UVA 2570

提示

样例输出 43 1 2 34 6 283 144 139 927438 927438 18 3 3 12 error 21 1 2 9 9 rejected 103 86 2 15 0 rejected 设目标数为limit；纸张上的数字为n；目前所有碎纸片上的最佳数字和为Max。试题要求将n按位的顺序拆分成若干个数，使其数和Max为不超过limit的最大数，并判断出数和为Max的拆分方案数r是1还是大于1，或者是根本无法拆分（r=0）。 那么，怎样求最佳数字和Max呢？

我们从n的最低位开始由右而左拆分，若当前拆分出i位数，则ni为当前碎纸片上的数字，剩余数字

?n?待拆分。拆分有两种情况： i???10? 不断开情况：当前碎纸片上的数字需继续向左扩展 断开情况：拆分出当前碎纸片上的数字

显然，我们可以采用回溯法分头递归这两种情况。设递归函数dfs(n,sum, now, k, p)，其中n为待拆分的数字，sum为已经拆分出的数和，当前待拆分出的一个数字为now，准备填入第k张碎纸片，p为下一个十进制位的权。 dfs(n,sum,now, k, p){

if (n==0){//若拆分完毕，则最后拆分出的数字now填入第k张纸条，更新答案并回溯 t[k]=now;

if (sum+now >limit) return; //若拆分出的数和大于目标数。则退出 if (sum+now==Max) r++; //若拆分出的数和相同于Max，则数和为Max的组合个数+1`

else if (sum+now >Max){ //若拆分出的数和更佳，则调整为max Max=sum+ now;

r=1; //数和为Max的组合数为1

ansk=k; //已填数的碎纸片数和各张碎纸片数的填数记入最佳方案 for (int i=1;i<=k;i++) ans[i]=t[i]; return; //回溯 }

int m=n; //取待拆分数的个位数 dfs(n/10,sum,now+p*m,k,p*10); //递归不断开的情况 t[k]=now; //now填入第k张碎纸片 dfs(n/10,sum+now,m,k+1,10); //递归断开后的情况 }

我们在主程序中初始化最佳数字和与组合数（Max=0; r=0），然后递归调用dfs(n/10,0,n,1,10)。若r>1，则说明拆分出数和为Max不止1个；若r=1，则max为最佳数字和，拆分出的数字为ans[ansk]‥ans[1]。

【29 Be Wary of Roses】

您为您获奖的玫瑰园非常骄傲。然而，一些嫉妒的同行园丁要不择手段地对付您。他们绑架了您，将您蒙上眼睛，并给您戴上手铐，然后将您丢在您所珍爱的玫瑰花丛中。您要逃出去，但您不能确保您可以不践踏珍贵的花朵。

幸运的是，您将您花园的布局记在脑中。这是一个N×N的平方图（N 为奇数），在其中的一些方格中种有玫瑰。您正好是站在平方图正中心的大理石基座上。不幸的是，你已经

完全迷失了方向，而且不知道您所面对的方向。大理石的基座可以让您调整您的方向，使得您朝向北，东，南，或西，但你没有办法知道您当前朝哪个方向。

无论您最初面朝哪个方向，您必须想出一个践踏尽可能少的玫瑰的逃离路径。您的路径必须从中心开始，只能水平和垂直移动，以离开方格作为结束。 输入：

每个测试用例首先在一行中给出平方图的大小N ( 1≤N≤21)；然后N行，每行N个字符，用于描述花园。`.' 表示方格中没有玫瑰，`R'表示方格中有玫瑰，而`P'代表在中心的大理石基座。

输入以N = 0为结束标志，程序不必进行处理。 输出：

对于每个测试用例，输出一行，给出在您逃离的时候要踩在玫瑰上的最少的次数。

样例输入 5 .RRR. R.R.R R.P.R R.R.R .RRR. 0 注： 试题来源：

在线测试：UVA 10798

提示

。。。。0、90、180、270 由于大理石的基座调整有四个方向：，因此设a[k][i][j]为地图旋转（k-1）。90*时（i,j）的状态，若（i,j）方格中有玫瑰，则a[k][i][j]=1；否则a[k][i][j]=0。

样例输出 At most 2 rose(s) trampled. 假设被踩玫瑰数的上限为limit，怎样判断你能否在踩到的玫瑰数不超过limit的情况下成功逃离玫瑰园呢？设

f[x][y][r1][r2][r3][r4]为行至（x,y）时，4个方向上踩到的玫瑰数分别为r1、r2、r3、r4的访问标志；

v[x][y]为已经过（x,y）的标志； flag为成功逃离的标志；

我们通过递归过程dfs(x,y,r1,r2,r3, r4)计算flag，其中（x,y）为目前行至的方格位置，4个方向上踩到的玫瑰数分别为r1、r2、r3、r4，显然经过（x,y）后，4个方向上踩到的玫瑰数增加至r1+a[1][x][y]，r2+a[2][x][y]，r3+a[3][x][y]，r4+a[4][x][y]。dfs(x,y,r1,r2,r3, r4)的计算过程如下：

dfs(x,y,r1,r2,r3, r4) {

if (flag) return; //成功退出

if (v[x][y]) return; //若先前经过（x,y），则回溯

if (max(r1,r2,r3,r4)>limit) return; //若任一方向上踩到的玫瑰数超过上限，则回溯 if (out(x,y)) { //若逃离玫瑰园，则成功退出 flag=1; return; }

if (f[x][y][r1][r2][r3][r4]) return; //若行至（x,y）、4个方向上踩到的玫瑰数为r1、r2、r3、r4的状态已访问，则回溯

f[x][y][r1][r2][r3][r4]=1; //设行至（x,y）、4个方向上踩到的玫瑰数为r1、r2、r3、r4的状态已访问

v[x][y]=1; //设（x,y）已经过标志

dfs(x+1,y,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]);//递归（x,y）的四个相邻方向

dfs(x-1,y,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); dfs(x,y+1,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); dfs(x,y-1,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); v[x][y]=0; //撤去（x,y）的经过标志 }

在dfs(x,y,r1,r2,r3, r4)的基础上，便可以计算逃离时踩到的最少玫瑰数： 计算出发位置（ox，oy）（ox=n/2+1,oy=n/2+1）； 成功标flag志初始化为0; // 被踩玫瑰数的上限/limit初始化为-1；

while (!flag){ //若未成功逃离，则被踩玫瑰数的上限+1 limit++;

f和v清零（memset(f,0,sizeof(f)); memset(v,0,sizeof(v))）;

dfs(ox,oy,0,0,0,0); //从图正中心出发，递归计算在被踩玫瑰数不超过上限的情况下逃离玫瑰园的可能性 }

输出逃离时踩到的最少玫瑰数limit；

【30 Monitoring the Amazon】

一个由独立的、用电池供电的、用于数据采集的站所组成的网络已经建成，用于监测Amazon地区的气候。发布指令的站将启动指令传输到测控站，使得它们改变其当前的参数。为了避免电池过载，每个站（包括发布指令的站）只能传送指令给另外两个站。通常是选择

与这个站最近的两个站。如果有多个站符合条件，则首先选择地图上的最西边（左边）的站，其次选择的最南端（在地图的最下方）的站。

你受Amazon州政府委托，编写一个程序，给出每个站的位置，确定是否信息可以传达到所有的站。 输入：

输入给出一个整数N，后面给出N对整数Xi, Yi，表示每个站的定位坐标。第一对坐标给出发布指令的站的位置，而剩下的N-1对是其他站的坐标。给出下述限制：-20≤Xi, Yi≤20, 以及 1≤N≤1000。输入以N= 0结束。 输出：

对每个给出的表达式，输出一行，指出是否所有的站都可以到达（见样例输出的格式）。

样例输入 4 1 0 0 1 -1 0 0 -1 8 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 6 0 3 0 4 1 3 -1 3 -1 -4 -2 -5 0 注：

试题来源：2004 Federal University of Rio Grande do Norte Classifying Contest - Round 1 在线测试：UVA 10687

提示

样例输出 All stations are reachable. All stations are reachable. There are stations that are unreachable. 设测控站为节点。根据题意（选择与这个站最近的两个站。如果有多个站符合条件，则首先选择地图上的最西边（左边）的站，其次选择的最南端（在地图的最下方）的站），每个节点k（0≤k≤n-1）的出度为2（若仅有一个测控站，则出度为1）。按照下述方法计算节点k的出边：

按照与节点k的欧式距离为第1关键字、x坐标为第2关键字、y坐标为第3关键字的递增顺序排列坐标序列w，节点k分别向节点w[1]和节点w[2]连边（若仅有一个测控站，则连边(k,w[1])）。

构造出有向图后，使用回溯法计算节点1（发布指令的站）可达的节点集合。若该集合囊括了除节点1外的所有节点，则表明信息可以传达到所有的站；否则表明存在未能接受信息的站。

【31 Graph Connectivity】

考虑一个无向图G = < V, E >。初始时图中无边。请写一程序判断两个不同节点间是否连通。程序还要有插入和删除边的功能。

本文来源：https://www.bwwdw.com/article/euzf.html