生活随笔
收集整理的這篇文章主要介紹了
实现BFS之“营救”
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
廣度優(yōu)先遍歷（Breadth First Search，BFS）是一個(gè)分層的搜索過(guò)程，沒有回退過(guò)程，是非遞歸的。
DFS與BFS的小秘密：
1、深度優(yōu)先搜索算法的思路很簡(jiǎn)單，比較好理解，但得到的解不是最優(yōu)的；而廣度優(yōu)先搜索則恰恰相反；
2、如果節(jié)點(diǎn)有無(wú)窮多個(gè)，深度優(yōu)先搜索算法在某處分支可以無(wú)限搜索下去卻找不到解，這時(shí)我們可以采用有界深度優(yōu)先搜索~
題目來(lái)源：
ZOJ Monthly，October 2003，ZOJ1649
題目描述：
Angel被MOLIGPY抓住了，她被關(guān)在監(jiān)獄里。監(jiān)獄可以用一個(gè)N*M的矩陣來(lái)描述，1<N、M<=200。監(jiān)獄由N*M個(gè)格子組成，每個(gè)方格中可能為墻壁、道路、警衛(wèi)、Angel或Angel的朋友。Angel的朋友想去營(yíng)救Angel。他的任務(wù)是接近Angel。約定“接近Angel”的意思是到達(dá)Angel被關(guān)的位置。如果Angel的朋友想到達(dá)某個(gè)方格，但方格中有警衛(wèi)，那么必須殺死警衛(wèi)，才能到達(dá)這個(gè)方格。假定Angel的朋友向上、下、左、右移動(dòng)一步用時(shí)1個(gè)單位時(shí)間，殺死警衛(wèi)也用時(shí)1個(gè)單位時(shí)間。假定Angel的朋友可以殺死所有警衛(wèi)。
試計(jì)算Angel的朋友接近Angel至少需要多長(zhǎng)時(shí)間，只能向上、下、左、右移動(dòng)，而且墻壁不能通過(guò)。
輸入描述：
輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)。每個(gè)測(cè)試數(shù)據(jù)的第1行為兩個(gè)整數(shù)N和M，接下來(lái)有N行，每行有M個(gè)字符："."代表道路，"a"代表Angel，"r"代表Angel的朋友，"#"代表墻壁，"x"代表警衛(wèi)。
輸出描述：
對(duì)每組測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)，表示接近Angel所需最少時(shí)間。如果無(wú)法接近Angel，則輸出"Poor ANGEL has to stay in the prison all his life."。
樣例輸入：
7 8
#.#####.
#a.#xr..
#.x#xx..
..xxxx.#
#.......
.#......
........
樣例輸出：
12
閑話少敘，奉上代碼+注釋~
Code：
[cpp]?view plaincopyprint?
#include<iostream>?? #include<queue>?? using?namespace?std;?? ?? #define?MAXN?200?? #define?INF?1000000?? ?? struct?point?? {?? ????int?x,?y;????????????????? ????int?step;????????????????? ????int?time;????????????????? };?? ?? queue<point>Q;?????????????????? ?? char?map[MAXN][MAXN];????????? int?mintime[MAXN][MAXN];?????? int?dir[4][2]?=?{?{-1,?0},?{0,?1},?{1,?0},?{0,?-1}?};????? int?N,?M;????????????????????? int?ax,?ay;??????????????????? ?? int?BFS(point?start)?? {?? ????int?i;?? ????Q.push(start);???????????? ????point?head;??????????????? ????while(!Q.empty())?? ????{?? ????????head?=?Q.front();????? ????????Q.pop();?????????????? ????????for(i?=?0;?i?<?4;?i++)?? ????????{?? ????????????int?x?=?head.x?+?dir[i][0],?y?=?head.y?+?dir[i][1];??????? ????????????if(x>=0?&&?x<N?&&?y>=0?&&?y<M?&&?map[x][y]?!=?'#')???????? ????????????{????? ????????????????point?next;?? ????????????????next.x?=?x;?? ????????????????next.y?=?y;?? ????????????????next.step?=?head.step?+?1;?? ????????????????next.time?=?head.time?+?1;?? ????????????????if(map[x][y]?==?'x')?next.time++;????? ?????????????????? ????????????????if(next.time?<?mintime[x][y])?? ????????????????{?? ????????????????????mintime[x][y]?=?next.time;?? ????????????????????Q.push(next);?? ????????????????}?? ????????????}?? ????????}?? ????}?? ????return?mintime[ax][ay];?? }?? ?? int?main()?? {?? ????int?i,?j;?? ????int?fx,?fy;??????? ????while(scanf("%d%d",?&N,?&M)?!=?EOF)?? ????{?? ????????memset(map,?0,?sizeof(map));?????????? ????????for(i?=?0;?i?<?N;?i++)?scanf("%s",?map[i]);???????? ????????for(i?=?0;?i?<?N;?i++)??? ????????????for(j?=?0;?j?<?M;?j++)??? ????????????{?? ????????????????mintime[i][j]?=?INF;?????????? ????????????????if(map[i][j]?==?'r')?{?fx?=?i;?fy?=?j;?}?? ????????????????else?if(map[i][j]?==?'a')?{?ax?=?i;?ay?=?j;?}?? ????????????}?? ????????point?start;?? ????????start.x?=?fx;?start.y?=?fy;?? ????????start.step?=?start.time?=?0;?? ????????mintime[fx][fy]?=?0;?? ????????int?mint?=?BFS(start);?? ????????if(mint?<?INF)?printf("%d\n",?mint);?? ????????else?printf("Poor?ANGEL?has?to?stay?in?the?prison?all?his?life.\n");?? ????}?? ????return?0;?? }??
運(yùn)行結(jié)果：
Ps：如有Bug，歡迎拍磚~
總結(jié)
以上是生活随笔為你收集整理的实现BFS之“营救”的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
