编程-计概a00-13综合习题计算机系代

综合习题-2014计算机系代亚非字符串法举例——循环数--2013循环数--2014描述n位的一个整数是循环数(cyclic)的条件是：当用一个1到n之间的整数去乘它时,会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说，如果把原来的数字和新的数字都首尾相接，他们得到的环是相同的。只是两个数的起始数字不一定相同。例如，数字

142857是循环数，因为:142857

*1

=

142857142857

*2

=

285714142857

*3

=

428571142857

*4

=

571428142857

*5

=

714285142857

*6

=

857142循环数-2014输入写一个程序确定给定的数是否是循环数。输入包括多个长度为2位到60

位的整数。(注意，先导的0也是合理的输入不应该被忽略,例如"01"是2位数，"1"是1位数。)输出对于每一个输入的整数，输出一行表明它是否是循环数。样例输入142857

142856

117647样例输出142857is

cyclic142856is not

cyclic142858is not

cyclic01

is not

cyclic分析：高精度计算，用字符串来做前导0不要去掉如果是循环数，乘积

过原来的n0588235294117647is

cyclic循环数-2014/*把以字符串形式表示的长为len的整数str乘上x*

若乘法溢出(最

前位)则不是循环数返回1*不溢出返回0*/bool

Mul(char

*str,

int

len,

int

x){

int

t

=

0;for

(int

i

=

len

-

1;

i

>=

0;

i

--){int

tmp

=

(str[i]

-

'0')

*

x

+

t;t

=

tmp

/

10;str[i]

=

tmp

%

10

+

‘0’;//t是进位部分//每个数字相乘后以字符保存}return(t>0);//最有溢出，返回1}56727*

5-----3----5int

main(){int

len;char

str[100],

tmp[100],pair[200];while

(cin

>>

str){len

=

strlen(str);strcpy(pair,

str);strcat(pair,

str);bool

cyclic

=

true;for

(int

i

=

2;

i

<=

len;

i

++){

strcpy(tmp,

str);if(Mul(tmp,len,i))//返回1有溢出{

cyclic=false;//乘法溢出,不是循环break;}//没有溢出，进一步检查是不是循环数else

if

(strstr(pair,

tmp)

==

NULL){

cyclic=false;//不是原串的循环break;}}cout

<<str<<"

is

"<<

(cyclic

?

"":

"not

")<<

"cyclic"

<<

endl;}return

0;}递归算法举例——碎纸机--2013碎纸机碎纸机有以下的特点每次切割之前，先要给定碎纸机一个目标数，而且在每张被送入碎纸机的纸片上也需要包含一个数。碎纸机切出的每个纸片上都包括一个数。要求切出的每个纸片上的数的和要不大于目标数而且与目标数最接近。碎纸机如图，假设目标数是50，输入纸片上的数是12346。碎纸机会把纸片切成4块，分别包含1，2，34，6。

1+2+34+6=43，这是所有的分割方式中，不超过50，而又最接近50的分割方式。又比如，分割成1，23，4，6是不正确的，1+23+4+6=34，比刚才得到的结果43小。分割成12，34，612+34+6=52，超过了50。碎纸机还有三个特别的规则：如果目标数和输入纸片上的数相同，那么纸片不进行切割。如果不论怎样切割，分割得到的纸片上数的和都大于目标数，么

显示错误信息。如果有多种不同的切割方式可以得到相同的最优结果。那么打印机显示服务信息。比如，如果目标数是15，输入纸片上的数是111，那么有两种不同的方式可以得到最优解，分别是切割成1和11或者切割成11和1，在这种情况下，会显示服务信息。为了设计这样的一个碎纸机，你需要先写一个简单的程序模拟这个

的工作。给定两个数，第一个是目标数，第二个是输入纸片上的数，你需要给出碎纸机对纸片的分割方式。碎纸机分析：为了处理方便，12345将数字按位存放在数组中能切出多少种组合？对于“12345”，共有5种切法1

，12+345,

123+45，

1234+5，

12345每切完“12345”一次，把问题交给后面的部分，等返回数据后相加。1什么时候递归结束？当切的位置到了字符串的末尾if

(np

>=

l){processing…;return;}11+234512+2+23+3453+4+545processing?完成一次切分，把分块累加，和已有的和比较，不符合则丢弃11+2保留1，a1[0]=1保留

，a1[1]

=21+2+3+45

保留3，a1[2]=31+

2

+

3

+

4

+

5保留4，a1[3]=41+2+3+4+5(完成一次切分)保留5，a1[4]=5

===========1+2+3+4+5=151+2+3+45=51(丢弃)1+2+34+5=42(替换15)1+2+345=348(丢弃)1+23+4+5=33(丢弃)……要有一个变量记录块数ap要有一个循环，把此次切分的块求和sumt=∑a1[i]要比较去次求和与前一次求和的结果，如果当前的更合适，做以下事情：保留sumt，a1数组，ap找到一组结果，cnt=1；碎纸机如果没有到达结束条件，继续递归调用函数的参数(当前且的位置np，已经得到的阶段和）从当前位置到末尾有多种切法，需要一个循环。for(int

i=np+1;i<=l;i++)在循环中，做以下几件事：把切下来的数据保存起来，假设在23和45之间切，将23保存起来，并且递归调用函数处理45。sum

*=10;sum+=a[i-1];//a中存放的是每一位数字如果sum+s已经大于给定的数，则没有必要再做下去了。保留当前切下的数据a1[ap]=sum，ap是切下来的块数继续递归调用时，累加和要加上本溪切下来的块的值sum23451

+当前位置是1，从2开始有4种切法123456a碎纸机#include<iostream>#include<cstring>

using

namespace

std;const

int

MAXN=7

//依题意，数字长度不超过6个字符int

a[MAXN];int

l

=

0;int

cnt

=

0;int

m;int

a1[MAXN];int

ap

=

0;int

ans[MAXN];int

ansp

=

0;int

anssum

=

0;//存放拆分出来的数据，最多拆出6个数据//字符串的实际长度//记录满足条件的最终和的个数//目标数//临时的数据段//临时的个数//最终的切分的数据段//最终的数字的个数//最终的和void

t(int

np,int

s)//np是当前切在字符串上的位置，s是当前得到的和{

if(np>=l)

//l是字符串的长度，切分到字符串最后了{

int

sumt

=

0;for

(int

i

=

0

;

i

<

ap

;

i++)sumt

+=

a1[i];//ap是数据段的个数//将切分出来的所有数据段求和//如果本次求和大于上一次的和，用更接近目标和的数替换anssumif

(anssum

<

sumt){

//以下逐条命令保存本次结果memcpy(ans,

a1,

sizeof(a1));

//保存当前

切分结果anssum=sumt;//保存当前新的和ansp

=

ap;

//保存当前切分出来的数据块的个数

值cnt=1;

//找到一种结果的标志为1}else

if

(anssum==

sumt)

有两次结果相同

t加1cnt++;//依题意，cnt大于1将不输出结果，return;

}//np没有到串末尾的情况int

sum=0;

//注意sum是局部变量//每次调用都可以认为一个新串，数据段长度从1到依次增加，//但是长度+起点 过总长度lfor

(int

i

=

np

+

1;

i

<=

l

;

i++){sum

*=

10;sum+=a[i-1];//a中存放的是每一位数字if(sum+s>m)//本次调用的和sum与前几次累加结果s之和超出目标数break;a1[ap++]=sum;//阶段和t(i,sum+s);

//递归

a1[--ap]=0;

//回溯}}int

main(){

cin

>>

m;while(m

!=

0)//测试数据的组数{

memset(ans,

0,

sizeof(ans));//最终答案数组清零//阶段数组清零//

输入m时的回车//依次读入字符串的单个字符memset(a1,

0,

sizeof(a1));ap

=

anssum

=

ansp

=

0;l

=

0;

cnt

=

0;

ap

=

0;cin.get();char

c

=

cin.get();while(c

!=

'\n'){

a[l++]=c-'0';//将字符转换成整数，并记录了串的长度lc=cin.get();}t(0,0);//两个参数分别代表切分的位置和当前的阶段和if

(cnt

==

1)

//{cout<<anssum;//输出总和

for(int

i=0;i<ansp;i++)cout<<''<<ans[i];//依次输出每个数字}else

if(cnt>1)//两种以上的结果cout

<<

"rejected";else//没有结果cout

<<

"error";cout

<<

endl;cin

>>

m;}return

0;}递归算法举例——分糖果问题--2012分糖果

的老师们为小朋友们准备了各种各样的糖果。不同的小朋友所喜欢的糖果可能是不同的，为了让

的小朋友得到他/她喜爱的糖果，

的老师们对小朋友们的“糖果偏好”(即哪位小朋友喜欢哪几种糖果)进行了统计。现已知老师们共准备了F(1≤F≤20)种糖果，准备为幼儿园里的N位小朋友(1≤N≤20)分配糖果。分糖果每位小朋友只会接受自己喜欢的糖果，不接受自己不喜欢的糖果；每种糖果只能分给某一位小朋友（即：一旦某种糖果分给某位小朋友，则其他小朋友就不能再被分配到该种糖果）；我们不保证所有小朋友都能获得糖果；每个小朋友喜欢哪种糖果将在输入数据中给出。写程序，将现有糖果分配给最多的小朋友。请输出可分到糖果的小朋友的最多的人数。每得出一种选择，记录人数，并比较是不是最多分糖果关于输入第1行为两个整数：N和F，以空格隔开。其中，N（1≤N≤100）表示小朋友的总人数；F（1≤F≤100）表示糖果的总种数（糖果种类分别用整数1,2,3,...,F进行）。接下来有N行，每行包含多个以空格隔开的整数；其中，第一个整数m，表示某位小朋友所喜爱的糖果的种数，其后的

m个整数，表示该小朋友所喜爱的糖果种类的序列。例如：若某行的输入为“3

1

2

3”，则表示该位小朋友共喜分别为“1”“2”“3”欢3种类型的糖果，其糖果类型。关于输出仅一行，即在上述输入条件下，能分到糖果的小朋友的人数的最大值。分糖果例子输入4

3(4个小朋友，3种糖果)2

12(第1号小朋友喜欢2种个糖果，分别是1,2)2

2

3(第2号小朋友喜欢2种个糖果，分别是2,3)2

132

13例子输出3分糖果分析：回顾八皇后、分书问题，和本题有什么相同？有什么不同？思考点：八皇后、分书和分书，都要有约束条件，用矩阵或向量表示。分书和分糖果都需要回溯0

1

2

3

40011011001011010001001001人

书ABCDE212223213213分糖果不同点：八皇后每行必须放一个棋子分书每人必须得到一本书分糖果不是每人都能得到糖果分糖果分析：如何结束递归？最后一个小朋友分完了kids==N+1;本题的特别要求，求人数最多的一次分配因此，每得到

案，就要保留最大的。如何记录分得糖果的小朋友的人数kids？将本次函数kids作为参数传递给子函数。分得糖果则小朋友加1。如何递归？f(candy

+

1，kids

+

1)f(candy

+

1，kids)分糖果如何读入每个人的

数据？for

(i

=

1;

i

<=

N;

i++){cin>>num;//喜欢的糖果数

for(j=1;j<=num;j++){cin>>k;

//喜欢的糖果号favor[i][k]=1;//喜好矩阵}}例子输入4

32

122

2

32101101constintasize

=

102;int

favor[asize][asize],done[asize];void

f(int,

int);int

N,

F,

largest;//N人，F水果

int

main(){int

i,j,

num,

k;cin

>>N>>

F;largest

=0;for(i=0;

i

<asize;i++){ done[i]=0;//初始化

for

(j=0;j<asize;j++)favor[i][j]=0;//初始化}for

(i

=

1;

i

<=

N;

i++){cin

>>

num;for

(j

=

1;

j

<=

num;

j++){cin

>>

k;favor[i][k]=1;//喜好矩阵}}f(1,

0);cout

<<

largest

<<endl;return

0;}void

f(int

kids,

int

cnt){

if(kids==N+1)//分到了最后一个{

if

(cnt

>

largest)largest

=

cnt;return;}f(kids+1，cnt);//当前的孩子不拿糖，人数不变//对于第p个小朋友，在F个水果中选favorfor(int

i=1;i<=F;i++){

if(done[i]==0

&&favor[kids][i]==1)

//满足选取条件{

done[i]

=

1;f(kids+1,cnt+1);//当前的孩子拿颗，人数加1，分下一个done[i]

=

0;

//回溯，清除记录，换

案}}}递归算法举例——计算字符串的相似度2012计算字符串的相似度一套操作方法来把两个不同的字符串变得相同。具体可选的操作方法有：修改一个字符，例如将"a"修改为"b"；增加一个字符，例如将"abdd"变为"aebdd"删除一个字符，例如将"travelling"变为"traveling"例如，对于两个字符串"abcdefg"和"abcdef"两个字符串来说，我们可以通过“将前一个字符串减少一个g”或者“给后一个字符串增加一个g”这两种方式来使得它们相同，这两种方案，都仅需要一次操作。将修改字符串操作需要的次数定义为两个字符串之间的距离，而相似度等于“距离+1”的倒数。例如，上例中"abcdefg"和"abcdef"的距离为1，则其相似度为1/2=0.5.计算字符串的相似度给定任意两个字符串(长度20以内)，写出一个程序来求出它们的相似度。关于输入第一行有一个整数n。表示测试数据的组数，接下来共n行，每行两个字符串，用空格隔开。表示要计算距离的两个字符串字符串长度不超过20。关于输出针对每一组测试数据输出两个字符串的相似度，保留小数点后6位。计算字符串的相似度处理,代价就是分析可能的情况：两个串同时结束，比较完毕一个串先结束，另一个串可按删除或者剩余的长度。两个串当前位置的字符相等，继续比较，不产生代价两个串当前位置的字符不相等不相等时可选择三种办法，删除、修改、

。两个串的比较当前位置是否相同，根据情况决定哪个串可以继续match(str1+X,str2+X);

//代表0或者1例如：match(str1+1,str2)or

match(str,str+1)计算字符串的相似度

#include

<iostream>#include

<iomanip>using

namespace

std;const

int

SIZE=100;int

f[SIZE][SIZE];char

a[100],

b[100];int

match(int,

int)计算字符串的相似度int

main(){

int

N;cin>>N;//有N组测试数据for

(int

k

=

0;

k

<

N;

k++){

for(int

m=0;

m<SIZE;m++)//每组数据都初始化数组

for

(int

n=0;

n<SIZE;n++)f[m][n]

=

INT_MAX;cin>>a>>b;

//输入字符串f[0][0]=match(0,0);//f[0][0]从两个串开始位置计算的代价cout

<<

fixed

<<

setprecision(6)<<1.0

/

(f[0][0]+1)<<endl;}return

0;}计算字符串的相似度int

match(int

i,

int

j){

if(f[i][j]!=INT_MAX)//已经计算过，直接返回代价

return

f[i][j];//先处理直接有结果的情况if(a[i]==‘\0’&&

b[j]==‘\0’)//a,b同时末尾匹配结束,不增加代价{

f[i][j]

=

0;

return

f[i][j];if

(a[i]

==

'\0')}//串a结束，b串剩余的长度即为代价。{

f[i][j]

=

strlen(b

+

j);

return

f[i][j];

}if

(b[j]

==

'\0')//串b结束，a串剩余的长度即为代价。{

f[i][j]

=

strlen(a

+

i);

return

f[i][j];

}if

(a[i]

==

b[j])//相比较的字符相等，这一步没有代价，其代价等于下//一个字符开始后面的比较产生的代价{

f[i][j]

=

match(i

+

1,

j

+

1);

return

f[i][j];

}计算字符串的相似度int

step[4]

=

{0,

0,

0,

0};//接下来是两个串的当前字符是不相等的情况//可以修改(abc,ebc)-->(ebc,abc)，代价为1；step[1]

=

1+

match(i

+

1,

j

+

1);//可以删除(aebc,ebc)-->(ebc,ebc)，代价为1;step[2]=1+match(i+1,j);//可以

(acd,abcd)-->(abcd,abcd)，代价为1；step[3]

=1

+

match(i,

j

+

1);for

(int

l=1;l<=3;l++)

//选择三个中代价最小的if

(step[l]

<

f[i][j])f[i][j]

=

step[l];return

f[i][j];//返回的是最小的，保存在f[i][j]中}int

main(){

char

c1[MAX],c2[MAX];cin

>>

n;while((n--)>0)int

n,

l1,

l2;{

cin.get();cin

>>

c1

>>

c2;l1

=

strlen(c1);l2

=

strlen(c2);if

(l1

>

l2)cout

<<

std::setprecision(6)

<<

fixed

<<1/((double)find(c2,c1,l2,l1,0,0)+1)

<<

endl;elsecout

<<

std::setprecision(6)

<<

fixed

<<1/((double)find(c1,c2,l1,l2,0,0)+1)

<<

endl;}return

0;

}int

find(char*

c1

,

char*

c2

,

int

l1,int

l2,int

p1,int

p2){if(p1==l1)//串c1到末尾

return

l2-p2;if(p2==l2)//串c1到末尾

return

l1-p1;int

ans;if

(c1[p1]

==

c2[p2])

//相等的情况，各自加1，没有代价ans

=

find(c1,c2,l1,l2,p1+1,p2+1);else

//不相等的情况只考虑修改和删除{ans

=

find(c1,c2,l1,l2,p1+1,p2+1)+1;int

ans2

=

find(c1,c2,l1,l2,p1,p2+1)+1;if

(ans

>

ans2)ans

=

ans2;}return

ans;}递归算法举例带有通配符的字符串匹配--2011带有通配符的字符串匹配-2011一个串带有通配符‘？’或‘*’，另一个串不包含通配符。？代表任意一个字符＊代表任意多个字符例1：1?456匹配10456,11456,12456…,1%456,…例2：1*456匹配111111456,12345678456，…带有通配符的字符串匹配从两个串首开始比较，同时向后扫描：如果当模式串p为空，待匹配串s也为空，则成功。*p

==‘\0’

&&*s

==‘\0’

；当串p和串s的首字符是普通字符，且两个字符相等，比较下一位，递归调用match(p+1,s+1)。如果两个字符不同，则失败。当串p的首字符是‘?’,可抵消串s的首字符，递归调用match(p+1,s+1)。当模式串的字符是‘*’，有三种情况：1、‘*’是最后一个字符，则完全匹配，直接返回true2、‘*’不是最后，让串s的后续各位都与p串‘*’后面的字符比较，只要找到一位相同，则可以继续比较下去。3、s串的所有位都比较过了，没有匹配到底，则失败。例2：1*456，123456784561234123412334123451?3568173456带有通配符的字符串匹配递归体现在哪里?原始的两个串，在匹配的过程中，不断去掉已经匹配的部分，把剩下的部分看成一个新问题，用同样的函数来求解。程序的设计用case语句来处理每种情况int

match(char

*pat,

char

*str){

int

i,

len

=

strlen(str);switch(*pat)//pat是模式串，str是待匹配串//串开始的字符{

case

'\0':return

*str

==

‘\0’;case

'?':if(*str

==

'\0')

return

0;return

match(pat

+

1,

str

+1);case

'*'://都是结尾成功，返回1;否则失败//越过首字符，重新来//‘*’是最后的字符，可匹配所有，不需再比较if

(*(pat

+

1)

==

‘\0’)return

1;return

0;default:if

(*pat

!=

*str)

return

0;for

(i

=

0;

i

<

len;

i++)if(match(pat+1,str+i))

//将待匹配的串的首字符不断的去掉return

1;//循环结束，都不匹配，返回假//没有特殊字符的情况下，不相等则失败return

match(pat+1,str+1);

//相等则继续}}带有通配符的字符串匹配int

main(){char

pat[20],

str[20];cin

>>

pat

>>

str;if

(match(pat,

str))cout

<<

"matched";elsecout

<<

"not

matched";return

0;}递归算法举例——城堡问题--2011城堡问题(图1)#

=Wall|

=

No

wall-

=

No

wall121

2

3

4

5

6

7##############################

|

#

|

#

|

|

######---#####---#---#####---##

#

|

#

#

#

#

##---#####---#####---#####---#图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m*n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。3#

|

|

#

#

#

#

##---#########---#####---#---#4

#

#

|

|

|

|

#

##############################南墙8北墙2西墙1东墙4城堡问题程序从标准输入设备读入数据。前两行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，

2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。关于输出城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。城堡问题2例子输入47116

116

3

10

67

9

6

13

5

15

5110

12

7

13

7

51

2

3

4

5

6

7#############################1

#

|

#

|

#

|

|

#3413南墙8#####---#####---#---#####---##

#

|

#

#

#

#

##---#####---#####---#####---##

|

|

#

#

#

#

##---#########---#####---#---##

#

|

|

|

|

#

##############################你编写一个程序，计算城堡一例子输出东墙城堡问题分析：子函数每个房间有4个方向，分别探测，每次都想检查是否越界请看4个方向的值，1,2,4,8，如果大于等于8，一定有南墙，先从南墙开始试探。如果方向值大于等于4，一定有东墙，南墙返回后，想东墙试探，….避免重复计数，走过的房间标注visit每当进入一个房间，房间数加1城堡问题分析：主函数每个房间作为起点，一次探测。如果遇到visit不为0，表明已经被

过，不作处理。开始一个新房间时，房间数的初值加，房间的面积初值为0，返回值为房间的总面积。从每个起点得到的房间的面积中，保留最大的。城堡问题const

int

SIZE

=

60;int

visit[SIZE][SIZE],

wall[SIZE][SIZE],

N,

M;int

main(){int

largest,

rooms,

cnt;cin

>>

N

>>

M;for

(int

i

=

1;

i

<=

N;

i++)for

(int

j

=

1;

j

<=

M;

j++){visit[i][j]

=

0;cin

>>

wall[i][j];}largest

=

0;

cnt

=

0;//每个房间为起点进行探测，如果visit不为0，//则越过，否则是一个新的房间的开始，计数加1for

(int

i

=

1;

i

<=

N;

i++)

for

(int

j

=

1;

j

<=

M;

j++)if

(visit[i][j]

==

0){

cnt++;rooms=mysearch(i,j,0);//从每个格子开始探测if

(rooms

>

largest)largest

=

rooms;}cout

<<

cnt

<<

endl;

cout

<<

largest

<<

endl;return

0;城堡问题int

mysearch(int

i,

int

j,

int

step){if

(visit[i][j]

!=

0)return

step;//已经走过，房间数不增加，返回else{visit[i][j]

=

1;step++;//来到新房间，记录到此一游//来到新的房间，房间数加1城堡问题//沿着房间的四个方向试探

if

(wall[i][j]>=8)wall[i][j]

-=

8;

//有南墙，不能往下走，去试其他三个方向else

//无南墙，且下面的房间没有走过，进入下面的房间{

if

(i

<

N

&&visit[i

+

1][j]

==

0)

//判断是否越界step

=

mysearch(i

+

1,

j,

step);}if

(wall[i][j]

>=

4)wall[i][j]

-=

4;else{

if

(j

<

M

&&visit[i][j

+

1]

==

0)step

=

mysearch(i,

j

+

1,

step);}if(wall[i][j]>=2)

//北墙

wall[i][j]-=2;else{

if

(i

>

1&&visit[i

-

1][j]

==

0)step

=

mysearch(i

-

1,

j,

step);}if

(wall[i][j]>=1)//西墙wall[i][j]

-=

1;else{

if

(j

>

1&&visit[i][j

-

1]

==

0)step

=

mysearch(i,

j

-

1,

step);}}return

step;//四个方向都探测，返回最终的房间数}递归算法举例——小

问题--2010小一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小。在一个分割成w

*

h个正

的矩形板上进行。

，每个正方格子上可以有一张

卡片，当然也可以没有。当下面的情况满足时，我们认为两个卡片之间有一条路径相连：路径只包含水平或者竖直的直线段。路径不能穿过别的卡片。但是允许路径临时的离开矩形板。下面是一个例子：小这里在(1,3)和(4,4)处的卡片是可以相连的。而在(2,3)和(3,4)处的卡是不相连的，因为连接他们的每条路径都必须要穿过别的卡片。你现在要在小里面判断是否存在一条满足题意的路径能连接给定的两个卡片。小输入包括多组数据。一个矩形板对应一组数据。每组数据包括的第一行包括两个整数w和h

(1

<=

w,

h

<=75)，分别表示矩形板的宽度和长度。下面的h行，每行包括w个字符，表示矩形板上的

卡片分布情况。使用‘X’表示这个地方有一个卡片；使用空格表示这个地方没有

卡片。之后的若干行上每行上包括4个整数x1,y1,x2,y2(1<=x1,x2<=w,1<=y1,y2<=h)。给出两个卡片在矩形板上的位置（注意：矩形板左上角的坐标是(1,

1)）。输入保证这两个卡片所处的位置是不相同的。如果一行上有4个0，表示这组测试数据的结束。如果一行上给出w=h=0，那么表示所有的输入结束了。小对每一个矩形板，输出一行“Board

#n:”，这里n是输入数据的

。然后对每一组需要测试的

卡片输出一行。这一行的开头是“Pair

m:”，这里m是测试卡片的 （对每个矩形板， 都从1开始）。接下来，如果可以相连，找到连接这两个卡片的所有路径中包括线段数最少的路径，输出“ksegments.”，这里k是找到的最优路径中包括的线段的数目；如果不能相连，输出“impossible.”。每组数据之后输出一个空行。5

4XXXXXX

XXXX

XXXX例子输出Board

#1:Pair

1:

4

segments.Pair

2:

3

segments.Pair

3:

impossible.2

3

5

300

0小分析属于周边邻居继续搜索的问题，例如滑雪，城堡，迷宫等。相似的步骤：用循环去四个方向试探，递归调用。记录到此一游for

(int

i=0;

i<4;i++)

//沿着四个方向搜索{tx

=

x

+

step[i][0];

ty

=

y

+

step[i][1];if

(tx

>=

0

&&tx

<=

h

+

1&&

ty

>=

0

&&ty

<=

w

+

1&&func(x1,

y1,

x2,

y2);!temp[tx][ty])1

1

右0

-1

左1

0

下-1

0

上小不同的地方边界多一圈如果方向不变，则不能算一步,所以多一个参数代表方向。要记录步数，再加一个参数，func(x,

y,

step，ex,

ey,

lasti);终止条件x==ex

&&y==ey小#include

<iostream>#include

<cstdlib>#include

<climits>using

namespace

std;bool

map[80][80],

temp[80][80];int

step[4][2]={{0,1