POJ搜索题目题解.docx
- 文档编号:13701896
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:49
- 大小:27.07KB
POJ搜索题目题解.docx
《POJ搜索题目题解.docx》由会员分享,可在线阅读,更多相关《POJ搜索题目题解.docx(49页珍藏版)》请在冰点文库上搜索。
POJ搜索题目题解
poj搜索题总结——初期篇
简单搜索
(1)深度优先搜索(poj2488,poj3009,poj1321)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414,poj2251,poj3083)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
看到这些题是不是很眼熟。
没错,这就是某位大牛推荐初期要做的题。
而这文章就是为这些题加上解题报告以及一些总结。
深度优先搜索
poj2488:
AKnight'sJourney
如果没有按字典序输出这个要求的话,就是简单的DFS,但是加上的话,就是麻烦题。
这就要求求出全部的走法或在行走时,按照某种顺序走。
从时间上来说,当然是选择第二种了。
若存在可行路线,则每个格子必然都走过。
所以从A1开始,按照某种顺序走,若有解,则为所求,若无,则无解。
//WA了N次,才发现是倒在字典序的手下
//虽然题目没说,但是这道题最后一组数据后是没有空行的...否则会PE...
//若存在可行路线,则每个格子都走过。
所以从(0,0)开始即可,不需要遍历每一个起始点//注意行走的方法(即MOV数组元素的排列),可以在找到可行解时,就使得其字典序最小
#include
#include
#include
usingnamespacestd;
boolflag;
stringanswer[30];
intchess[30][30];
//这个的设置一定要与下面的转换相对应,之前就是不对应,错了N次
intmov[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
stringGetPosition(intx,inty){//将X,Y坐标转换成题目要求的形式
stringstmp;
stmp+=(char)(y+'A');//由于先出现的是Y坐标(如B3),所以MOV数组中的Y应从-2到2的顺序变化
stmp+=(char)(x+'1');
returnstmp;
}
voidSaveIt(intp,intq){//保存下答案
for(inti=0;i
for(intj=0;j answer[chess[i][j]]=GetPosition(i,j); } } } voiddfs(intp,intq,intnum,intx,inty){ if(num==p*q){ flag=true; SaveIt(p,q); return; } intxx,yy; for(inti=0;i<8;++i){ if(flag)return; xx=x+mov[i][0]; yy=y+mov[i][1]; if((xx>=0&&xx =0&&yy chess[xx][yy]=num+1; dfs(p,q,num+1,xx,yy); chess[xx][yy]=0; } } } intmain(){ ifstreamcin("test.in"); intcases,count (1),p,q,i; cin>>cases; while(cases--){ cin>>p>>q; flag=false; memset(chess,0,sizeof(chess)); chess[0][0]=1; dfs(p,q,1,0,0); //output cout<<"Scenario#"< "< if(flag){ for(i=1;i<=p*q;++i)cout< cout< } elsecout<<"impossible"< if(cases! =0)cout< } return0; } poj1321: 棋盘问题 这题是简单的DFS,但题目有个地方说得不是很清楚,就是以“#”为标志的位置才能放棋子。 //一次AC,用了DFS,以递归回溯的形式实现题目说得有点不清楚,以“#”为标志的位置才能入棋子 #include #include usingnamespacestd; intcount; intchess[8][8];//能放棋子为1,不能为0,放下棋子的是2 boolIsLegal(intx,inty){//由于一行只放一个,所以不用判断是否同行,这里只判断是否同列 for(inti=0;i if(chess[i][y]==2){ returnfalse; } } returntrue; } voiddfs(intn,intk,intnum,intstart){//num表示当前放了几颗棋子,START表示放棋子的超始行数 if(num==k){ ++count; return; } for(inti=start;i for(intj=0;j if(chess[i][j]&&IsLegal(i,j)){ chess[i][j]=2; dfs(n,k,num+1,i+1); chess[i][j]=1;//还原,很重要 } } } } intmain(){ ifstreamcin("test.in"); charctmp; intn,k; while(cin>>n>>k&&n! =-1){ memset(chess,0,sizeof(chess)); for(inti=0;i for(intj=0;j cin>>ctmp; if(ctmp=='#'){ chess[i][j]=1; } } } count=0; dfs(n,k,0,0); cout< } return0; } 广度优先搜索 DFS一般是用来求全部解。 但可以使其按照某种方式前进而达到求最优解的目的。 而BFS则常用于求最优解,但其缺陷是空间要求过大。 用BFS还有一个易错点,就是队列空间申请得过小(特别是用循环数组),导致有一些情况判断来不及判断就被覆盖掉。 POJ1321: CatchThatCow 这题如果是用循环数组做的话,一定要注意我说的那个易错点。 //做BFS的第一题(用了类,STL中的队列),写完后,提交,TLE==不用STL中的队列再加上剪枝后,就不TLE了,但一直RE==(数组越界)不RE,然后又WA,发现这情况: 0100000不能判断因为队列数组开得太小了,把还没来得及处理的数据给覆盖掉了改大后,才AC掉,阴险题 #include //#include usingnamespacestd; constintQMAX=50000; classNODE{ public: NODE(intxx=0,intss=0): x(xx),step(ss){} intx; intstep; }; boolwalk[200001];//数组一定要足够大,否则RE NODEq[QMAX];//队列 intmove[3][2]={{1,1},{1,-1},{2,0}};//移动的方法 intmain(){ //ifstreamcin("test.in"); ints,t,now,total,itmp; while(cin>>s>>t){ now=0; total=1; memset(walk,0,sizeof(walk)); //BFS q[now]=NODE(s,0); walk[s]=true; while(now! =total){ if(q[now%QMAX].x==t){ cout< break; } for(inti=0;i<3;++i){ itmp=(q[now%QMAX].x*move[i][0])+move[i][1]; if(itmp<=200000&&itmp>=0&&! walk[itmp]){//先判断ITMP范围,否则RE walk[itmp]=true; q[(total++)%QMAX]=NODE(itmp,q[now%QMAX].step+1); } } ++now; } } return0; } POJ1426: FindTheMultiple #include #include //#include usingnamespacestd; constintQMAX=10000;//定义队列最大长度 boolIsMultiple(stringstr,intn){//判断STR能否被N整除 intlen,mul,itmp; mul=10; itmp=0; len=str.size(); for(inti=0;i itmp=itmp*mul+(str[i]-'0'); if(itmp continue; } else{ itmp=itmp%n; if(itmp==0){ returntrue; } } } returnfalse; } intmain(){ ifstreamcin("test.in"); intn,now,total; stringstmp; stringq[QMAX]; charletter[2]={'0','1'}; while(cin>>n&&n! =0){ now=0; total=1; //bfs q[now]="1"; while(now! =total){ if(IsMultiple(q[now%QMAX],n)){ cout< break; } for(inti=0;i<2;++i){ q[(total++)%QMAX]=q[now%QMAX]+letter[i]; } ++now; } } return0; } POJ3126PrimePath 也可以说是简单的BFS题。 但有一点是注意的是SQRT函数可是被重载过。 使用时,一定要指明其类型。 BFS题,先求出全部四位的素数,然后再逐个尝试提交后CE,原来是SQRT函数作怪然后是WA,原因是素数判断错误,应该是J<=SQRT(I),而不是J #include #include //#include usingnamespacestd; classNODE{ public: NODE(intnn=0,intss=0): num(nn),step(ss){} intnum; intstep; }; constintPMAX=2000; constintQMAX=9000; intprime[PMAX]; boolselect[PMAX]; NODEq[QMAX]; voidinit(int&len){//算出全部的素数 boolflag; for(inti=1000;i<9999;++i){ flag=true; for(intj=2;j<=sqrt((double)i);++j){//注意SQRT有多个版本 if(i%j==0){ flag=false; break; } } if(flag){ prime[len++]=i; } } } boolIsLegal(intnum1,intnum2){//判断是否符合题目要求 intdif(0); while(num1! =0){ if(num1%10! =num2%10){ ++dif; } if(dif>1){ returnfalse; } num1/=10; num2/=10; } returntrue; } intmain(){ //ifstreamcin("test.in"); boolflag; intcases,n,m,len(0),now,total; init(len); cin>>cases; while(cases--){ cin>>n>>m; memset(select,0,sizeof(select)); //bfs now=0; total=1; flag=false; q[now]=NODE(n,0); while(now! =total){ if(q[now%QMAX].num==m){ cout< flag=true; break; } for(inti=0;i if(! select[i]&&IsLegal(q[now%QMAX].num,prime[i])){ q[(total++)%QMAX]=NODE(prime[i],q[now%QMAX].step+1); select[i]=true; } } ++now; } if(! flag){ cout<<"Impossible"< } } return0; } POJ3414: Pots 相比起之前的BFS题,不同点就只有输出路径。 这时只要在类中多加一个变量来记录上一步是哪个步骤。 但要注意,不要用循环数组,因为会把前面的一些值给覆盖掉。 //bfs,简单题,注意怎样回溯出使用了哪些步骤就可以了 //第一次WA,不能过的数据: 9110095答案是170 //错误原因: walk数组开小了,导致有一些情况不能判断 //从100X100改为201X201后就AC了 #include #include #include #include usingnamespacestd; constintQMAX=9000; classNODE{ public: NODE(intx1=0,intx2=0,intx3=0,intx4=0): a(x1),b(x2),method(x3),pre(x4){} inta; intb; intmethod;//记录是用什么方法得到这步 intpre;//记录前一个步骤是哪个(数组的下标),回溯时用到 }; NODEq[QMAX];//队列数组开大点,不要用循环数组 boolwalk[201][201];//注意最大应该是200,就是这里开小了,导致WA stringstr[7]={"","FILL (1)","FILL (2)","DROP (1)","DROP (2)","POUR(1,2)","POUR(2,1)"}; intmain(){ ifstreamcin("test.in"); boolflag; inta,b,c,now,total,count; while(cin>>a>>b>>c){ memset(walk,0,sizeof(walk)); now=0; total=1; flag=false; walk[0][0]=true; q[now]=NODE(0,0,0,0); while(now! =total){ if(q[now].a==c||q[now].b==c){ flag=true; break; } //fill if(q[now].a! =a&&! walk[a][q[now].b]){//method=1meansFILL (1) q[total++]=NODE(a,q[now].b,1,now); walk[a][q[now].b]=true; } if(q[now].b! =b&&! walk[q[now].a][b]){//method=2meansFILL (2) q[total++]=NODE(q[now].a,b,2,now); walk[q[now].a][b]=true; } //drop if(q[now].a! =0&&! walk[0][q[now].b]){//method=3meansDROP (1) q[total++]=NODE(0,q[now].b,3,now); walk[0][q[now].b]=true; } if(q[now].b! =0&&! walk[q[now].a][0]){//method=4meansDROP (2) q[total++]=NODE(q[now].a,0,4,now); walk[q[now].a][0]=true; } //pour if(q[now].a! =0&&q[now].b! =b){//method=5meansPOUR(1,2) if(q[now].a+q[now].b>=b&&! walk[q[now].a-(b-q[now].b)][b]){ q[total++]=NODE(q[now].a-(b-q[now].b),b,5,now); walk[q[now].a-(b-q[now].b)][b]=true; } else{ if(q[now].a+q[now].b walk[0][q[now].a+q[now].b]){ q[total++]=NODE(0,q[now].a+q[now].b,5,now); walk[0][q[now].a+q[now].b]=true; } } } if(q[now].a! =a&&q[now].b! =0){//method=6meansPOUR(2,1) if(q[now].a+q[now].b>=a&&! walk[a][q[now].b-(a-q[now].a)]){ q[total++]=NODE(a,q[now].b-(a-q[now].a),6,now); walk[a][q[now].b-(a-q[now].a)]=true; } else{
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- POJ 搜索 题目 题解