搜索题目类型各题总结-acm

《搜索题目类型各题总结-acm》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一个让人感觉很复杂的BFS（但是并不很复杂）问题D:BFS_连连看游戏时间限制:2Sec内存限制:5MB提交:12解决:3[提交][状态][讨论版]题目描述大家都玩过连连看吧！今天我们玩一个类似的游戏。在一个由10*10个小方格组成的矩形里有n(n<=10)对字符(它们是大写字符中的前n个)。矩形里有些位置是可以从上面走过，有些则不能。能走过的位置用'.'标识，不能的用'#'标识。如果2个相同字符是连通的(从一个字符能走到另一个字符，注意走的时候只能向上、下、左、右走。某个位置是有其他字符时，这个

2、位置是不能走的)，那么这对字符能够进行配对。如果将这对字符配对，这对字符将从这个矩形里消除，也就是说这2个字符所在的位置对于其他字符而言变成能走动了。现在的问题是：请你决定这些字符的配对顺序(只有能配对才能进行配对)，使得n对字符最后都配对成功。输入先给出一个正整数t(t<=10)，表示有t组测试数据。每组测试数据有10行组成，每行有10个字符。这些字符只能是'.'，'#'，或者是大写字符中的前n个。每组测试数据中不超过10对字符。输出如果能够使每组测试数据中的n对字符配对成功，输出配对的顺序。如

3、果有多种配对成功的顺序，输出字典序最小的那组。否则输出"MyGod!"。样例输入2ABF.......CE........D..........................................................D........EC.......FBAABF.......CE........D......................................#........#D.........#........EC.......FBA样例输出DCABEF

4、MyGod!参考了下老师的代码其实我一直的思路也都是这样的而且还动手写了但是都是写到一半的时候放弃了因为心里畏惧害怕超时还害怕复杂以后做一个题目的时候要是有一定的把握就不要畏惧不要婆婆妈妈的大大方方的把代码敲出来干掉它#include#include#includeusingnamespacestd;intstep[4][2]={-1,0,1,0,0,-1,0,1};charmap[11][11];intused[11][11];charans[

5、20];structhaha{intx;inty;intstep;friendbooloperator<(structhahaa,structhahab){returna.step>b.step;}}q,temp;intBFS(intx,inty){intx1,y1,i;priority_queueque;memset(used,0,sizeof(used));q.x=x;q.y=y;q.step=0;used[x][y]=1;que.push(q);while(!que.

6、empty()){temp=que.top();que.pop();for(i=0;i<4;i++){x1=temp.x+step[i][0];y1=temp.y+step[i][1];if(x1>=0&&x1<10&&y1>=0&&y1<10&&!used[x1][y1]&&(map[x1][y1]=='.'

7、

8、map[x1][y1]==map[x][y])){if(map[x1][y1]==map[x][y]){map[x1][y1]='.';map[x][y]='.';return1;}q.

9、x=x1;q.y=y1;q.step=temp.step+1;que.push(q);used[x1][y1]=1;}}}return0;}intmain(){intcas,k;while(scanf("%d",&cas)!=EOF){while(cas--){inti,j,end=0,end2,flag=0,cnt=0;for(i=0;i<10;i++)scanf("%s",map[i]);while(!end){for(k='A';k<='M'&&!end;k++)/*借鉴老师的方法感觉比较好

10、一开始就是怕处理太麻烦不敢下手其实只要试着去做的时候才会发现其实没那么复杂*/{end2=0;for(i=0;i<10&&!end2;i++)for(j=0;j<10&&!end2;j++)//这个终止方法好漂亮啊省去了一堆break以前的方法太笨了{if(map[i][j]==k){if(BFS(i,j)){ans[cnt++]=k;end=end2=1;}elseend2=1;}}}if(end==0)break;end=0;}for(i=0;i<10;i++)for(j=0;