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

/*宝葫芦问题解题报告题目：宝葫芦被放在一个城堡里。城堡由n*m个方格组成，你只能从当前所在的方格跳到相邻的4个方格里，而且不能跳出城堡的范围。城堡中某些方格里有弹簧，每个弹簧具有一个特定能量p，不同弹簧的p值不一定相同。如果你跳到一个有弹簧的方格，就会立刻沿着原来运动的方向继续跳p格，如果跳到的方格里又有弹簧，就马上继续跳，直到跳到一个空的方格或者被墙挡住无法继续前进为止。你能否尽快找到宝葫芦吗？输入：第一行有两个整数，n和m(3=n,m=100)，分别是城堡的行数和列数。其后是一个非负整数k，表示弹簧的个数。在接下来的k行里，每行有三个正数x, y, p，以空格隔开，其中x和y是弹簧的坐标(2=x=n-1, 2=y=m-1)，p是弹簧的能量。在下面的两行里，分别是你和宝葫芦的坐标。此外，你在空中经过的弹簧对你没有任何影响。已知你、宝葫芦和弹簧的初始位置都不同。x坐标轴的范围是1到n，y坐标轴的范围是1到m。有多组测试用例。输出：最少的步数，或者impossible题目来源：bit网络教室解题思路：首先明确这是一个搜索问题，并且不需要记录路径，那么就不需要要用深搜(dfs)，并且深搜需要搜索完所有的点才能却确定出最小的解，这个代价是很大的，所以应该选择广搜（bfs）。在搜索的时候，建立队列，把人的起点都放在队列的开始，然后从它开始搜索，搜都的点放在队列里，然后从队列里取值搜索，直到到搜到宝葫芦为止，最少的步数就是搜索的层数，若果搜索完队列里的所有元素，还没有找到宝葫芦，那么就是impossible。需要注意的细节：1）当你跳到弹簧的时候，一定要把此次弹簧跳的终点存在队列里，而不是把弹簧的坐标存在队列里面。2）弹簧可能被用多次，跳过之后不要删附上代码，仅供参考：*/#include#include#define N 105int n,m,flag;int front,rear;int springNN,mapNN,ppN*N;/spring弹簧，map标记是否搜过，0-还没碰过，1-看到了，2-搜过了；pp该点至少跳几次才到struct pointint x;int y;struct point end,pN*N;void findlast(int &p1,int &p2,int fang1,int fang2)/如果遇到弹簧，那么需要找到最终的落点int a=p1,b=p2;p1+=fang1*springab;p2+=fang2*springab;if(p1n)p1=n;return;if(p2m)p2=m;return;if( springp1p2=0 )return;else findlast(p1,p2,fang1,fang2);int search(int a,int b)if( a=end.x & b=end.y )return 1;elseint tag=ppfront+1;/tag无其他还以，只是ppfront+1需要用很多次，为了简便，下同if(b-10&mapab-1=0)if(springab-10)/判断是否有弹簧，下同int p1=a,p2=b-1;findlast(p1,p2,0,-1);/找到最终的落点，最终的落点就是要存在队列里的点，0，-1,表示此时搜索方向，下同if(mapp1p2=0)prear.x=p1;prear.y=p2;pprear+=tag;mapp1p2=1;elseprear.x=a;prear.y=b-1;pprear+=tag;mapab-1=1;if(a-10&mapa-1b=0)if(springa-1b0)int p1=a-1,p2=b;findlast(p1,p2,-1,0);if(mapp1p2=0)prear.x=p1;prear.y=p2;pprear+=tag;mapp1p2=1;elseprear.x=a-1;prear.y=b;pprear+=tag;mapa-1b=1;if(a+10)int p1=a+1,p2=b;findlast(p1,p2,1,0);if(mapp1p2=0)prear.x=p1;prear.y=p2;pprear+=tag;mapp1p2=1;+rear;elseprear.x=a+1;prear.y=b;pprear+=tag;mapa+1b=1;if(b+10)int p1=a,p2=b+1;findlast(p1,p2,0,1);if(mapp1p2=0)prear.x=p1;prear.y=p2;pprear+=tag;mapp1p2=1;elseprear.x=a;prear.y=b+1;pprear+=tag;mapab+1=1;return 0;int main()int k,i,j;while(scanf(%d%d%d,&n,&m,&k)!=EOF)for(i=1;i=n;+i)for(j=1;j=m;+j)springij=0;mapij=0;while(k-)scanf(%d%d,&i,&j);/输入弹簧坐标scanf(%d,&springij);/输入该弹簧能量front=0;rear=1;scanf(%d%d%d%d,&pfront.x,&pfront.y,&end.x,&end.y);/输入起点和终点，即是你的位置和宝葫芦的位置ppfront=0;while(f