bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx

bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx

ID:52563532

大小:15.09 KB

页数:5页

时间:2020-03-28

bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx_第1页
bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx_第2页
bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx_第3页
bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx_第4页
bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx_第5页
资源描述:

《bfs解决宝葫芦问题——解题报告+广搜(bfs)算法.docx》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、/*宝葫芦问题解题报告题目:宝葫芦被放在一个城堡里。城堡由n*m个方格组成,你只能从当前所在的方格跳到相邻的4个方格里,而且不能跳出城堡的范围。城堡中某些方格里有弹簧 ,每个弹簧具有一个特定能量p,不同弹簧的p值不一定相同。如果你跳到一个有弹簧的方格,就会立刻沿着原来运动的方向继续跳p格,如果跳到的方格里又有 弹簧,就马上继续跳,直到跳到一个空的方格或者被墙挡住无法继续前进为止。你能否尽快找到宝葫芦吗?输入:第一行有两个整数,n和m(3=

2、示弹簧的个数。在接下来的k行里,每行有三个正数x,y, p,以空格隔开,其中x和y是弹簧的坐标(2=

3、所有的点才能却确定出最小的解,这个代价是 很大的,所以应该选择广搜(bfs)。在搜索的时候,建立队列,把人的起点都放在队列的开始,然后从它开始搜索,搜都的点放在队列里,然后从队列里取值搜 索,直到到搜到宝葫芦为止,最少的步数就是搜索的层数,若果搜索完队列里的所有元素,还没有找到宝葫芦,那么就是impossible。需要注意的细节:1)当你跳到弹簧的时候,一定要把此次弹簧跳的终点存在队列里,而不是把弹簧的坐标存在队列里面。2)弹簧可能被用多次,跳过之后不要删附上代码,仅供参考:*/#include

4、.h>#include#defineN105intn,m,flag;intfront,rear;intspring[N][N],map[N][N],pp[N*N];///spring[][]弹簧,map[][]标记是否搜过,0-还没碰过,1-看到了,2-搜过了;pp[]该点至少跳几次才到structpoint{intx;inty;};structpointend,p[N*N];voidfindlast(int&p1,int&p2,intfang1,intfang2)//如果遇到弹簧,那么需要

5、找到最终的落点{inta=p1,b=p2;p1+=fang1*spring[a][b];p2+=fang2*spring[a][b];if(p1<=0){p1=1;return;}if(p1>n){p1=n;return;}if(p2<=0){p2=1;return;}if(p2>m){p2=m;return;}if(spring[p1][p2]==0)return;elsefindlast(p1,p2,fang1,fang2);}intsearch(inta,intb){if(a==end.x&&b==e

6、nd.y)return1;else{inttag=pp[front]+1;///tag无其他还以,只是pp[front]+1需要用很多次,为了简便,下同if(b-1>0&&map[a][b-1]==0){if(spring[a][b-1]>0)////判断是否有弹簧,下同{intp1=a,p2=b-1;findlast(p1,p2,0,-1);////找到最终的落点,最终的落点就是要存在队列里的点,0,-1,表示此时搜索方向,下同if(map[p1][p2]==0){p[rear].x=p1;p[rear]

7、.y=p2;pp[rear++]=tag;map[p1][p2]=1;}}else{p[rear].x=a;p[rear].y=b-1;pp[rear++]=tag;map[a][b-1]=1;}}if(a-1>0&&map[a-1][b]==0){if(spring[a-1][b]>0){intp1=a-1,p2=b;findlast(p1,p2,-1,0);if(map[p1][p2]==0){p[rear].x=p1;p[rear].y=p2;pp[rear++]=tag;map[p1][p2]=1;

8、}}else{p[rear].x=a-1;p[rear].y=b;pp[rear++]=tag;map[a-1][b]=1;}}if(a+1<=n&&map[a+1][b]==0){if(spring[a+1][b]>0){intp1=a+1,p2=b;findlast(p1,p2,1,0);if(map[p1][p2]==0){p[rear].x=p1;p[rear].y=p2;pp[rear++]=tag;m

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。