一个让人感觉很复杂的BFS（但是并不很复杂）问题 D: BFS_连连看游戏时间限制: 2 Sec 内存限制: 5 MB提交: 12 解决: 3提交状态讨论版题目描述大 家都玩过连连看吧！今天我们玩一个类似的游戏。在一个由10*10个小方格组成的矩形里有n(n=10)对字符(它们是大写字符中的前n个)。矩 形里有些位置是可以从上面走过，有些则不能。能走过的位置用.标识，不能的用#标识。如果2个相同字符是连通的(从一个字符能走到另一个字符，注 意走的时候只能向上、下、左、右走。某个位置是有其他字符时，这个位置是不能走的)，那么这对字符能够进行配对。如果将这对字符配对，这对字符将从这个矩 形里消除，也就是说这2个字符所在的位置对于其他字符而言变成能走动了。现在的问题是：请你决定这些字符的配对顺序(只有能配对才能进行配对)，使得n对字符最后都配对成功。输入先给出一个正整数t(t=10)，表示有t组测试数据。每组测试数据有10行组成，每行有10个字符。这些字符只能是.，#，或者是大写字符中的前n个。每组测试数据中不超过10对字符。输出如果能够使每组测试数据中的n对字符配对成功，输出配对的顺序。如果有多种配对成功的顺序，输出字典序最小的那组。否则输出My God!。样例输入2ABF.CE.D.D.EC.FBAABF.CE.D.#.#D.#.EC.FBA样例输出DCABEFMy God!参考了下老师的代码 其实我一直的思路也都是这样的 而且还动手写了 但是都是写到一半的时候放弃了 因为心里畏惧 害怕超时还害怕复杂 以后做一个题目的时候要是有一定的把握就不要畏惧 不要婆婆妈妈的 大大方方的把代码敲出来 干掉它#include#include#includeusing namespace std;int step42=-1,0,1,0,0,-1,0,1;char map1111;int used1111;char ans20;struct haha int x; int y; int step; friend bool operator b.step; q,temp;int BFS(int x,int y) int x1,y1,i; priority_queueque; memset(used,0,sizeof(used); q.x=x;q.y=y;q.step=0; usedxy=1; que.push(q); while(!que.empty() temp=que.top(); que.pop(); for(i=0;i=0&x1=0&y110&!usedx1y1&(mapx1y1=.|mapx1y1=mapxy) if(mapx1y1=mapxy) mapx1y1=.; mapxy=.;return 1; q.x=x1; q.y=y1; q.step=temp.step+1; que.push(q); usedx1y1=1; return 0;int main() int cas,k; while(scanf(%d,&cas)!=EOF) while(cas-) int i,j,end=0,end2,flag=0,cnt=0; for(i=0;i10;i+) scanf(%s,mapi); while(!end) for(k=A;k=M&!end;k+)/*借鉴老师的方法感觉比较好 一开始就是怕处理太麻烦不敢下手其实只要试着去做的时候才会发现其实没那么复杂*/ end2=0; for(i=0;i10&!end2;i+) for(j=0;j10&!end2;j+)/这个终止方法好漂亮啊 省去了一堆break 以前的方法太笨了 if(mapij=k) if(BFS(i,j) anscnt+=k;end=end2=1; else end2=1; if(end=0) break; end=0; for(i=0;i10;i+) for(j=0;j10;j+) if(mapij!=.&mapij!=#) flag=1;break; if(flag) printf(My God!n); else for(i=0;icnt;i+) printf(%c,ansi); printf(n); return 0;Civil WarAccepted : 43Time Limit : 1000 MS Description战争即和平，自由即奴役，无知即力量。乔治.奥威尔 历史书上说，自从统治者Big Brother去 世以后，大洋国就陷入了无休止的内战中，随时都可能有新的武装势力出现，随时都可能有战争发生。奇怪的是，每次战争都是在当前国内战斗力最强大的两股势力 间进行，我们可以把每股武装势力的战斗力量化成一个值，每次战争都是在当前战斗力值最高的两股势力间进行。如果有多支势力战斗力值相同，则名字字典序大的 在前（见下面第二组样例）。一场战争结束后，战斗力稍弱的那方被消灭，另一方也元气大伤，战斗力减弱为两支武装的战斗力之差。如果发生战争的两方战斗力相 同，则他们会同归于尽。 历史书上详细记录了该段时期的事件，记录分为两种格式： 1) New name value 其中name和value是变量，表示一个名字叫做name，战斗力为value的新势力出现2) Fight 表示在当前最强的两股势力间发生了战争 现在请你根据书上记录，计算出每场战争以后分别导致哪支（或哪两支）势力被消灭。 输入 输入的第一行包含一个整数T (T 15)，表示共有T组数据。接下来每组数据的第一行是一个整数N (N 50000)，表示有N条记录。接下来N行，每行表示一条记录，记录的格式如上所述。输入保证每股势力的名字都不相同，势力的名字仅包含小写字母，长度不超过20。战斗力值为不超过10000的正整数。保证当战争发生时至少有两支势力存在。 输出 对每组数据，输出一行“Case X:”作为开头，此处X为从1开始的编号。注意首字母C为大写，在“Case”和编号X之间有一个空格，在编号X后面有一个冒号。然后对每条Fight记录输出一行，表示被消灭的势力的名字。如果是两支势力同归于尽，则这两个名字都应该输出，字典序大的在前，两个名字之间用一个空格隔开。 样例输入 2 5 New obrien 100 New winston 199 Fight New julia 99 Fight 4 New miniluv 100 New minipax 100 New minitrue 100 Fight 样例输出 Case 1: obrien winston julia Case 2: