bfs解決寶葫蘆問題——解題報(bào)告+廣搜(bfs)算法

1、/*寶葫蘆問題解題報(bào)告題目：寶葫蘆被放在一個(gè)城堡里。城堡由n*m個(gè)方格組成，你只能從當(dāng)前所在的方格跳到相鄰的4個(gè)方格里，而且不能跳出城堡的范圍。城堡中某些方格里有彈簧，每個(gè)彈簧具有一個(gè)特定能量p，不同彈簧的p值不一定相同。如果你跳到一個(gè)有彈簧的方格，就會(huì)立刻沿著原來運(yùn)動(dòng)的方向繼續(xù)跳p格，如果跳到的方格里又有彈簧，就馬上繼續(xù)跳，直到跳到一個(gè)空的方格或者被墻擋住無法繼續(xù)前進(jìn)為止。你能否盡快找到寶葫蘆嗎？輸入：第一行有兩個(gè)整數(shù)，n和m(3=n,m=100)，分別是城堡的行數(shù)和列數(shù)。其后是一個(gè)非負(fù)整數(shù)k，表示彈簧的個(gè)數(shù)。在接下來的k行里，每行有三個(gè)正數(shù)x, y, p，以空格隔開，其中x和y是彈簧的坐標(biāo)

2、(2=x=n-1, 2=y=m-1)，p是彈簧的能量。在下面的兩行里，分別是你和寶葫蘆的坐標(biāo)。此外，你在空中經(jīng)過的彈簧對(duì)你沒有任何影響。已知你、寶葫蘆和彈簧的初始位置都不同。x坐標(biāo)軸的范圍是1到n，y坐標(biāo)軸的范圍是1到m。有多組測(cè)試用例。輸出：最少的步數(shù)，或者impossible題目來源：bit網(wǎng)絡(luò)教室解題思路：首先明確這是一個(gè)搜索問題，并且不需要記錄路徑，那么就不需要要用深搜(dfs)，并且深搜需要搜索完所有的點(diǎn)才能卻確定出最小的解，這個(gè)代價(jià)是很大的，所以應(yīng)該選擇廣搜（bfs）。在搜索的時(shí)候，建立隊(duì)列，把人的起點(diǎn)都放在隊(duì)列的開始，然后從它開始搜索，搜都的點(diǎn)放在隊(duì)列里，然后從隊(duì)列里取值搜索，直

3、到到搜到寶葫蘆為止，最少的步數(shù)就是搜索的層數(shù)，若果搜索完隊(duì)列里的所有元素，還沒有找到寶葫蘆，那么就是impossible。需要注意的細(xì)節(jié)：1）當(dāng)你跳到彈簧的時(shí)候，一定要把此次彈簧跳的終點(diǎn)存在隊(duì)列里，而不是把彈簧的坐標(biāo)存在隊(duì)列里面。2）彈簧可能被用多次，跳過之后不要?jiǎng)h附上代碼，僅供參考：*/#include#include#define N 105int n,m,flag;int front,rear;int springNN,mapNN,ppN*N;/spring彈簧，map標(biāo)記是否搜過，0-還沒碰過，1-看到了，2-搜過了；pp該點(diǎn)至少跳幾次才到struct pointint x;int y

4、;struct point end,pN*N;void findlast(int &p1,int &p2,int fang1,int fang2)/如果遇到彈簧，那么需要找到最終的落點(diǎn)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;elsei

5、nt tag=ppfront+1;/tag無其他還以，只是ppfront+1需要用很多次，為了簡(jiǎn)便，下同if(b-10&mapab-1=0)if(springab-10)/判斷是否有彈簧，下同int p1=a,p2=b-1;findlast(p1,p2,0,-1);/找到最終的落點(diǎn)，最終的落點(diǎn)就是要存在隊(duì)列里的點(diǎn)，0，-1,表示此時(shí)搜索方向，下同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(

6、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;m

7、apa+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);/輸入彈簧坐標(biāo)scanf(%d,&springij);/輸入該彈簧能量front=0;rear=1;scanf(%d%d%d%d,&pfront.x,&pfront.y,&end.x,&end.y);/輸入起點(diǎn)和終點(diǎn)，即是你的位置和寶葫蘆的位置ppfront=0;while(f