算法實訓(第7學期)_第05周_分支限界法實例(新版,更正了以前的錯誤)

1、湖南涉外經(jīng)濟學院信息科學與工程學院鄒競1分支限界法分支限界法是一種廣度優(yōu)先的搜索策略。它在包含問題的所有解的解空間樹中，按照廣度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹，在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索解空間樹。在搜索問題的解空間樹時，分支限界法與回溯法對

2、當前擴展結(jié)點所使用的擴展方式不同。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有孩子結(jié)點。在這些孩子結(jié)點中，那些導致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點被舍棄，其余孩子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所求的解或活結(jié)點表為空時為止。2隊列式分支限界法和優(yōu)先隊列式分支限界法從活結(jié)點表中選擇下一擴展結(jié)點的方式通常有以下兩種：1、隊列式(FIFO)分支限界法：隊列式分支限界法將活結(jié)點表組織成一個隊列，并按隊列的先進先出原則選取下一個結(jié)點為當前擴展結(jié)點，因為沒有提示信息，所以搜

3、索具有一定的盲目性，效率不高。2、優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，交按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的高低與p值大小相關(guān)，根據(jù)問題的不同情況，采用大根堆或小根堆來描述優(yōu)先隊列。用一個大根堆來實現(xiàn)最大優(yōu)先隊列，體現(xiàn)最大效益優(yōu)先的原則；用一個小根堆來實現(xiàn)最小優(yōu)先隊列，體現(xiàn)最小費用優(yōu)先的原則。曾經(jīng)學過的例子：單源點最短路徑問題、裝載問題、縱橫布線問題、0-1背包問題、最大團問題、旅行商問題、圓排列問題。Description在一個大小為h行w列（1=

4、w,h=75）的矩形棋盤的每一個小方格中，可能放了一張游戲牌也有可能沒放。兩張游戲牌能夠連接起來當且僅當滿足下列條件：（1）從一張游戲牌到另一張游戲牌的連線，由若干水平或垂直線段構(gòu)成；（2）這些線段中任何一條都不能穿越其他游戲牌，但棋盤邊界外的線段可以不在棋盤內(nèi)。你的任務是：對于給定的棋盤布局，以及指定的兩張游戲牌，判斷是否存在一條滿足上述條件的線路將他們連接起來，并且若存在這樣的線路，求出需要的線段數(shù)最少的線路。例如，圖中第2列第3行的牌，能夠和第5列第3行的牌連接，第1列第3行的牌，能夠和第4列第4行的牌連接，而第3列第2行的牌不能夠和第3列第4行的牌連接。題目來源：http:/poj.o

5、rg/problem?id=1101Input：The input contains descriptions of several different game situations. The first line of each description contains two integers w and h (1 = w,h = 75), the width and the height of the board. The next h lines describe the contents of the board; each of these lines contains exac

6、tly w characters: a X if there is a game piece at this location, and a space if there is no game piece.Each description is followed by several lines containing four integers x1, y1, x2, y2 each satisfying 1 = x1,x2 = w, 1 = y1,y2 = h. These are the coordinates of two game pieces. (The upper left cor

7、ner has the coordinates (1, 1).) These two game pieces will always be different. The list of pairs of game pieces for a board will be terminated by a line containing 0 0 0 0.The entire input is terminated by a test case starting with w=h=0. This test case should not be procesed.Output：For each board

8、, output the line Board #n:, where n is the number of the board. Then, output one line for each pair of game pieces associated with the board description. Each of these lines has to start with Pair m: , where m is the number of the pair (starting the count with 1 for each board). Follow this by kseg

9、ments., where k is the minimum number of segments for a path connecting the two game pieces, or impossible., if it is not possible to connect the two game pieces as described above.Output a blank line after each board.Sample Input5 4XXXXXX XXXX X XXX2 3 5 31 3 4 42 3 3 40 0 0 00 0Sample OutputBoard

10、#1:Pair 1: 4 segments.Pair 2: 3 segments.Pair 3: impossible.分析：要求的是最少線段數(shù)（也就是拐彎數(shù)減要求的是最少線段數(shù)（也就是拐彎數(shù)減1 1）。采用隊列式分支限界法，隊列元素節(jié)點包含當前位置、已經(jīng)經(jīng)過的線段數(shù)。算法開始時，從第1張牌的位置，沿著上下左右4個方向搜索。由于要求拐彎次數(shù)最少，因此，當沿著某個方向搜索時，應該將沿途經(jīng)過的位置（如果可以有連線經(jīng)過）的相關(guān)信息入隊列（也就是換方向以前要將原方向的可以有連線的位置入隊列），即當某一個位置的坐標(x,y)依舊在棋盤內(nèi)，并且該坐標位置沒有游戲牌，并且坐標(x,y)以前沒有搜索過，則生成

11、相應的節(jié)點插入隊列，并將坐標(x,y)標記為已訪問。隨后循環(huán)進行如下操作：如果隊列元素為空，則說明沒有通路，無解，否則從隊列當中獲取隊首節(jié)點出隊列，如果該節(jié)點正好對應第二張游戲牌的坐標，則找到了一個解，否則，按照上下左右4個方向搜索，在改變方向以前將某一方向上可以有連線的位置入隊列。反復循環(huán)，直到找到解或者確定無解。/作者：鄒競/版本：1.0/日期：2010-07-21#include #include #include #include using namespace std;struct QNode /優(yōu)先隊列節(jié)點 int x, y; /當前格子的行、列 int pri; /線段數(shù);cla

12、ss Gameprotected: int w, h; /棋盤高度、寬度 char *board; /boardij = W表示有卡片（障礙物），boardij = 表示沒有卡片 int *grid; /gridij = 0表示第i行第j列還沒有被搜索，gridij = 1表示第i行第j列已經(jīng)被搜索過 vector pair pair, pair v; /保存輸入的兩張卡片的坐標 vector s; /保存結(jié)果 static int dir42; /4個方向public: Game(int hh, int ww); Game(); bool InBoard(int x, int y); /判斷

13、i行j列是否在棋盤內(nèi) void ReadData(); int Process(int x, int y, int ea, int eb); /返回從第x行第y列到第ea行第eb列的最小線段數(shù) void Process(); void Output();int Game:dir42 = -1, 0 , 0, 1 , 1, 0 , 0, -1 ;Game:Game(int hh, int ww) w = ww; h = hh; board = new char*h + 2; for (int i = 0; i h + 2; i+) boardi = new charw + 2; for (int

14、 i = 0; i h + 2; i+) for (int j = 0; j w + 2; j+) boardij = ; grid = new int*h + 2; for (int i = 0; i h + 2; i+) gridi = new intw + 2;Game:Game() for (int i = 0; i h + 2; i+) delete boardi; delete board; board = NULL; for (int i = 0; i = 0 & x = 0 & y w + 2;void Game:ReadData() int i = 0, j

15、= 0, a = 0, b = 0; pair pair, pair p; v.clear(); cin.get(); for (i = 1; i i j a b; while (i != 0 & j != 0 & a != 0 & b != 0) p.first.first = j; p.first.second = i; p.second.first = b; p.second.second = a; v.push_back(p); cin i j a b; int Game:Process(int x, int y, int ea, int eb) queue q

16、; QNode newnode, oldnode; for (int i = 0; i h + 2; i+) for (int j = 0; j w + 2; j+) gridij = 0; newnode.x = x; newnode.y = y; newnode.pri = 0; q.push(newnode); gridxy = 1; while(!q.empty() oldnode = q.front(); q.pop(); if (oldnode.x = ea & oldnode.y = eb) return oldnode.pri; /找到最優(yōu)解 for (int i =

17、0; i 4; i+) /4個方向試探 for (int k = 1; ; k+) newnode.x = oldnode.x + k * diri0; newnode.y = oldnode.y + k * diri1; newnode.pri = oldnode.pri + 1; if (newnode.x = ea & newnode.y = eb) return newnode.pri; if (!InBoard(newnode.x, newnode.y) break; /越界 if (gridnewnode.xnewnode.y = 1) break; /好馬不吃回頭草 if

18、 (boardnewnode.xnewnode.y = X & (newnode.x != ea | newnode.y != eb) break; /有障礙 q.push(newnode); gridnewnode.xnewnode.y = 1; return -1;void Game:Process() int iend = v.size(); s.clear(); for (int i = 0; i iend; i+) int k = Process(vi.first.first, vi.first.second, vi.second.first, vi.second.secon

19、d); s.push_back(k); void Game:Output() int iend = s.size(); for (int i = 0; i -1) cout Pair i + 1 : si segments.n; else cout Pair i + 1 w h; while (h != 0 & w != 0) cnt+; Game g(h, w); g.ReadData(); g.Process(); cout Board # cnt :n; g.Output(); cout w h; return 0;Holedox是一種奇怪的蛇，它的窩很像一個迷宮，可以假設其形狀

20、為n*m的矩形網(wǎng)格，每個網(wǎng)格的大小為1*1，窩出口的行列坐標為(1,1)。在每一個網(wǎng)格內(nèi)，可能有一塊無法移動的石頭，也可能什么也沒有，Holedox就盤踞在窩中若干空白網(wǎng)格內(nèi)。Holedox身體長度為L，可以用B1(r1,c1) B2(r2,c2) . BL(rL,cL) 來表示它的身體, 其中Bi和Bi+1 （1 = i =L-1）處在窩中上下左右相鄰的兩個網(wǎng)格內(nèi)，B1是它的頭部， BL是它的尾部。當Holedox爬行時，Holedox先選擇一個與其頭部所在網(wǎng)格相鄰的網(wǎng)格，如果這個網(wǎng)格內(nèi)沒有石頭，且Holedox身體的任何一段都不在這個網(wǎng)格內(nèi)，則它的頭部就能進入這個網(wǎng)格，同時，B Bi i進

21、入原先進入原先B Bi-1i-1所在的網(wǎng)所在的網(wǎng)格（格（2=i=L2=i=L）。For example, in the Figure 2, at the beginning the body of Holedox can be represented as B1(4,1) B2(4,2) B3(3,2)B4(3,1). During the next step, observing that B1(5,1) is the only square that the head can be moved into, Holedox moves its head into B1(5,1), then

22、moves B2 into B1, B3 into B2, and B4 into B3. Thus after one step, the body of Holedox locates in B1(5,1)B2(4,1)B3(4,2) B4(3,2) (see the Figure 3). 你的任務是，給定Holedox窩的描述和Holedox在窩中的初始狀態(tài)，編程求出Holedox的頭部爬行到出口所需要的最少步數(shù)。出口在最左上方的那個網(wǎng)格(1,1)。題目來源：/problem?id=1324Input輸入包含多個測試用例。每一個測試用例的第一行包含3個整數(shù)n,

23、m (1=n, m=20) 和 L (2=L=8)，分別表示矩形洞穴的網(wǎng)格的行數(shù)和列數(shù)，以及Holedox的身體所占的網(wǎng)格數(shù)。接下來又L行數(shù)據(jù)，表示Holedox身體的每一個網(wǎng)格的位置，順序從 B1(r1,c1) 到BL(rL,cL) ，其中 1=ri=n, and 1=ci=m,1=i=L。接下來的一行包含一個整數(shù)K，表示矩形洞穴的石頭所占的網(wǎng)格數(shù)。接下來的K行表示每個石頭所占的網(wǎng)格的行號和列號。然后，以空行分隔每個測試用例，最后一行的0 0 0表示測試用例結(jié)束。 Note: Bi is always adjacent to Bi+1 (1=i=L-1) and exit square (1

24、,1) will never be a stone. OutputFor each test case output one line containing the test case number followed by the minimal number of steps Holedox has to take. -1 means no solution for that case.Sample Input5 6 44 14 23 23 132 33 33 44 4 42 31 31 42 442 12 23 44 20 0 0Sample OutputCase 1: 9Case 2:

25、-1分析：采用隊列式分支限界法，隊列元素為當前搜索到的Holedox的某種狀態(tài)（Holedox身體所在的網(wǎng)格的坐標，以及蛇頭從初始網(wǎng)格到當前網(wǎng)格移動了多少個網(wǎng)格）。引入向量v，存儲搜索過的Holedox的狀態(tài)。將Holedox的初始狀態(tài)插入隊列。然后進行如下循環(huán)：如果隊列為空，則說明Holedox無法到達出口。否則，將隊首元素出隊列，如果該元素對應的Holedox身體的蛇頭所在的網(wǎng)格就是出口所在的網(wǎng)格，則找到了一個解，否則，對該元素按照上下左右四個方向擴展子節(jié)點，如果能到到達某個方向的下一個網(wǎng)格（該網(wǎng)格與當前元素蛇頭所在的網(wǎng)格相鄰，并且不是該網(wǎng)格不是Holedox身體的一部分，并且該網(wǎng)格沒有石

26、頭），則讓Holedox朝該網(wǎng)格移動，更新Holedox的狀態(tài)，并生成相應的隊列節(jié)點插入到隊尾。當反復循環(huán)，直到找到解或者確定無解。如何記錄蛇當前的狀態(tài)，以避免以后重復的訪問變成了關(guān)鍵，在這里我們將蛇的狀態(tài)描述為如下三元組（x,y,state）,其中(x,y)是蛇頭的坐標，state記錄的是尾巴的狀態(tài)，由于尾巴最長為7段，每一段相對于前一段只有上下左右四種狀態(tài)，僅需要兩位表示，則尾巴狀態(tài)最多需要72=14位二進制數(shù)表示，則我們可以構(gòu)建矩陣flag212116384來保存訪問過的狀態(tài)，以避免重復訪問相同的狀態(tài)。#include #include #include using namespace

27、std;struct QNodeint l;int* snake;int step;QNode();QNode(int l);QNode(const QNode& rhs);QNode();QNode& operator=(const QNode& rhs);QNode:QNode() l = 0; snake = NULL; step = 0;QNode:QNode(int l)this-l = l; step = 0; snake = new int*l;for (int i = 0; i l; i+) snakei = new int2;QNode:QNode()

28、 for (int i = 0; i l; i+) delete snakei; delete snake;QNode:QNode(const QNode& rhs)l = rhs.l; step = rhs.step; snake = new int*l;for (int i = 0; i l; i+) snakei = new int2;for (int i = 0; i l; i+)for (int j = 0; j 2; j+) snakeij = rhs.snakeij;QNode& QNode:operator=(const QNode& rhs)l = r

29、hs.l; step = rhs.step; snake = new int*l;for (int i = 0; i l; i+) snakei = new int2;for (int i = 0; i l; i+)for (int j = 0; j m = m; this-n = n; this-l = l; map = new int*m; for (int i = 0; i m; i+) mapi = new intn; snake = new int*l; for (int i = 0; i l; i+) snakei = new int2;HoledoxMoving:HoledoxM

30、oving() for (int i = 0; i m; i+) delete mapi; delete map; for (int i = 0; i l; i+) delete snakei; delete snake;void HoledoxMoving:ReadData() for (int i = 0; i m; i+) for (int j = 0; j n; j+) mapij = 0; for (int i = 0; i r c; snakei0 = r - 1; snakei1 = c - 1; cin k; for (int i = 0; i r c; mapr-1c-1 =

31、 1; bool HoledoxMoving:CanArrive(int x, int y, int* snake) const if (!(x = 0 & x = 0 & y n) | (mapxy != 0) return false; for (int i = 0; i ny) return 0; else return 1; else if (px nx) return 2; else return 3; int HoledoxMoving:GetState(int* snake) const int s = 0; for (int i = 0; i l - 1; i+

32、) s = s * 4 + location(snakei0, snakei1, snakei + 10, snakei + 11); return s;int HoledoxMoving:BFS() int* flag = new bool*m; for (int i = 0; i m; i+) flagi = new bool*n; for (int j = 0; j n; j+) flagij = new bool1 (2*(l-1); queue q; QNode current(l); for (int i = 0; i l; i+) current.snakei0 = snakei

33、0; current.snakei1 = snakei1; current.step = 0; int state = GetState(current.snake); q.push(current); flagcurrent.snake00current.snake01state = true; while (!q.empty() QNode current = q.front(); q.pop(); if (current.snake00 = 0 & current.snake01 = 0) for (int i = 0; i m; i+) for (int j = 0; j n;

34、 j+) delete flagij; delete flagi; delete flag; return current.step; for (int i = 0; i 0; j-) next.snakej0 = current.snakej - 10; next.snakej1 = current.snakej - 11; next.snake00 = x; next.snake01 = y; next.step = current.step + 1; int state = GetState(next.snake); if (flagxystate) continue; q.push(n

35、ext); flagxystate = true; for (int i = 0; i m; i+) for (int j = 0; j m n l; while (m 0 & n 0 & l 0) HoledoxMoving obj(m, n, l); obj.ReadData(); cout Case Case+ : obj.BFS() m n l; return 0;此代碼的算法流程正確，但是提交發(fā)現(xiàn)超時。超時的原因在于：1、大量的new、delete在堆空間對內(nèi)存動態(tài)分配和回收占用了大量時間；2、STL的queue在時間上沒有優(yōu)勢。將程序修改如下：#include #i

36、nclude #includeusing namespace std;struct QNode int l; int snake82; int step;const int dir42 = -1,0,0,1,1,0,0,-1 ;bool flag20201 14;QNode qu1 20;void ReadData(int m, int n, int l, int map20, int snake2) for (int i = 0; i m; i+) for (int j = 0; j n; j+) mapij = 0; for (int i = 0; i r c; snakei0 = r -

37、 1; snakei1 = c - 1; int k = 0; cin k; for (int i = 0; i r c; mapr-1c-1 = 1; bool CanArrive(int m, int n, int l, int map20, int x, int y, int snake2) if (!(x = 0 & x = 0 & y n) | (mapxy != 0) return false; for (int i = 0; i ny) return 0; else return 1; else if (px nx) return 2; else return 3

38、; int GetState(int l, int snake2) int s = 0; for (int i = 0; i l - 1; i+) s = s * 4 + location(snakei0, snakei1, snakei + 10, snakei + 1 1); return s;int BFS(int m, int n, int l, int map20, int snake2) for (int i = 0; i m; i+) for (int j = 0; j n; j+) for (int k = 0; k 1 (2 * (l - 1); k+) flagijk =

39、false; int head = 0, end = 0; QNode current; for (int i = 0; i l; i+) current.snakei0 = snakei0; current.snakei1 = snakei1; current.step = 0; int state = GetState(l, current.snake); quend+ = current; flagcurrent.snake00current.snake01state = true; while (head end) QNode current = quhead+; if (curren

40、t.snake00 = 0 & current.snake01 = 0) return current.step; for (int i = 0; i 0; j-) next.snakej0 = current.snakej - 10; next.snakej1 = current.snakej - 11; next.snake00 = x; next.snake01 = y; next.step = current.step + 1; int state = GetState(l, next.snake); if (flagxystate) continue; quend+ = ne

41、xt; flagxystate = true; return -1;int main() int Case = 1, m = 0, n = 0, l = 0; int map2020; snake82; cin m n l; while (m 0 & n 0 & l 0) ReadData(m, n, l, map, snake); cout Case Case+ : BFS(m, n, l, map, snake) m n l; return 0;Description RMI現(xiàn)在正嘗試用機器人搬運物品。機器人的形狀是一個直徑1.6米的球。在試驗階段，機器人被用于在一個儲藏室

42、中搬運貨物。儲藏室是一個N*M的網(wǎng)格，有些格子為不可移動的障礙。機器人的中心總是在格點上，機器人必須在最短的時間內(nèi)把物品搬運到指定的地方。機器人接受的指令有：1、向前移動1步（Creep）；2、向前移動2步（Walk）；3、向前移動3步（Run）；4、向左轉(zhuǎn)（Left）；5、向右轉(zhuǎn)（Right）。 每個指令所需要的時間為1秒。請你計算一下機器人完成任務所需的最少時間。題目來源：/problem?id=1376Input 輸入的第一行為兩個正整數(shù)N,M（N,M=50），下面N行是儲藏室的構(gòu)造，0表示無障礙，1表示有障礙，數(shù)字之間用一個空格隔開。接著一行有四個整數(shù)和一個大

43、寫字母，分別為起始點和目標點左上角網(wǎng)格的行與列，起始時的面對方向（東E，南S，西W，北N），數(shù)與數(shù)，數(shù)與字母之間均用一個空格隔開。終點的面向方向是任意的。Output 輸出整數(shù)，表示機器人完成任務所需的最少時間。 如果無法到達，輸出-1。Sample Input9 100 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 1 00 0 0 1 0 0 0 0 0 00 0 1 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 00 0 0 0 0 1 0 0 0 00 0 0 1 1 0 0 0 0 00 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0

44、 0 1 07 2 2 7 south0 0Sample Output12分析：采用優(yōu)先隊列式分支限界法，隊列元素節(jié)點信息包含機器人當前位置、機器人面部方向和已經(jīng)使用的時間，隊列元素優(yōu)先級就是已經(jīng)使用的時間單位。算法開始時，將機器人的初始信息（包括初始位置、面朝方向、以及已經(jīng)使用的時間單位0）插入優(yōu)先隊列。隨后循環(huán)進行如下操作：如果隊列元素為空，則說明沒有通路，無解，否則從優(yōu)先隊列當中獲取優(yōu)先級最高的節(jié)點（已使用時間單位最小的節(jié)點）出隊列，如果該節(jié)點正好對應目的地坐標，則找到了一個解，否則，依次嘗試讓機器人執(zhí)行5種命令中的一種，如果該命令可以執(zhí)行（如沒有障礙物阻攔，沒有超越邊界），并且該狀態(tài)（

45、包括機器人當前位置、面朝方向）以前沒有搜索過，則生成相應的節(jié)點插入優(yōu)先隊列，并置該節(jié)點對應的狀態(tài)的搜索標志為已搜索。反復循環(huán)，直到找到解或者確定無解。這里，還要解決2個細節(jié)問題：（1）機器人的中心總是在格點上，并且只能沿著格點構(gòu)成的線段移動，并非沿著網(wǎng)格內(nèi)移動，這樣可以看成機器人所在的位置總是在某個網(wǎng)格(i,j)的右下角（0in-2, 0jm-2）。（2）機器人的狀態(tài)不僅包含位置坐標，還應該包含面朝的方向。如果要判斷某個狀態(tài)是否曾經(jīng)被搜索過，可以引入三維數(shù)組state，stateijk表示坐標(i,j)，機器人面朝方向k是否已經(jīng)被搜索過。#include #include #include #

46、include using namespace std;struct QNode int x, y; int f; int t; bool operator (const QNode &rhs) const;bool QNode:operator rhs.t;class Poj1376protected: int m, n; int* maze; bool* state; int endx, endy; /終點 QNode robot; static int dir42;public: Poj1376(int mm, int nn); Poj1376(); void ReadData(

47、); int BFS();int Poj1376:dir42 = -1,0,0,1,1,0,0,-1 ; /上右下左Poj1376:Poj1376(int mm, int nn) m = mm; n = nn; maze = new int*m; for (int i = 0; i m; i+) mazei = new intn; state = new bool*m; for (int i = 0; i m; i+) statei = new bool*n; for (int j = 0; j n; j+) stateij = new bool4; Poj1376:Poj1376() for

48、 (int i = 0; i m; i+) for (int j = 0; j n; j+) delete stateij; delete statei; delete state; for (int i = 0; i m; i+) mazei; delete maze;void Poj1376:ReadData() for (int i = 0; i m; i+) for (int j = 0; j mazeij; int x = 0, y = 0; cin x y; robot.x = x - 1; robot.y = y - 1; cin x y; endx = x - 1; endy

49、= y - 1; string ch; cin ch; switch (ch0) case n: case N: robot.f = 0; break; case e: case E: robot.f = 1; break; case s: case S: robot.f = 2; break; case w: case W: robot.f = 3; break; default: break; robot.t = 0;int Poj1376:BFS() priority_queue q; for (int i = 0; i m; i+) for (int j = 0; j n; j+) f

50、or (int k = 0; k 4; k+) stateijk = 0; q.push(robot); staterobot.xrobot.yrobot.f = 1; while (!q.empty() QNode current = q.top(); q.pop(); if (current.x = endx & current.y = endy) return current.t; QNode next = current; for (int k = 1; k = 3; k+) next.x = current.x + k * dircurrent.f0; next.y = cu

51、rrent.y + k * dircurrent.f1; next.f = current.f; next.t = current.t + 1; if (next.x = m - 1 | next.y = n - 1) break; bool flag = false; for (int i = min(current.x, next.x); i = max(current.x, next.x); i+) for (int j = min(current.y, next.y); j = max(current.y, next.y); j+) if (mazeij = 1 | mazei + 1

52、j = 1 | mazeij + 1 = 1 | mazei + 1j + 1 = 1) flag = true; break; if (flag) break; if (flag) break; if (statenext.xnext.ynext.f = 0) q.push(next); statenext.xnext.ynext.f = 1; next = current; next.f-; if (next.f m n; while (m 0 & n 0) Poj1376 obj(m, n); obj.ReadData(); cout obj.BFS() m n; return

53、0;怪盜基德成功盜取了寶石，正在向自己的基地撤退。但由于后面有著一群追兵，在名偵探毛利小五郎和中村警部的率領(lǐng)下窮追不舍。所以基德要盡快地返回基地，否則就會被對手逮住。終于基德來到了最后的一站：關(guān)東原野，穿過這里就可以回到基地了。然而敵人依然緊追不舍。不過，關(guān)東的地理條件對基德十分有利，眾多的湖泊隨處分布。對手需要繞道而行，但基德?lián)碛猩衿娴幕枰恚沟盟茌p松快速的飛越湖面。當然，為了保證安全起見，基德還是決定找一條能最快回到基地的路。假設關(guān)東原野是一個m*n矩陣，它有兩種地，P表示平地，L表示湖泊?；轮荒芡Ａ粼谄降厣希壳暗奈恢迷谧笊辖?1, 1)處，而目的地為右下角的(m, n)，基德可

54、以向前后左右4個方向移動或者飛行，每移動1格需要1單位時間，而飛行的時間主要花費在變形上，飛行本身時間消耗很短，所以無論一次飛行多遠的距離，都只需要1單位時間。飛行的途中不能變向，并且一次飛行最終必須要降落在平地上。由于滑翔翼受到能量的限制，基德不能無限制的飛行，他總共最多可以飛行的距離為D。在知道了以上的信息后，請你幫助基德計算一下，他最快到達基地所需要的時間。輸入輸入輸入包含多個測試案例。每個測試案例的開頭一行是3個非負整數(shù)m（1m100）、n（1n100）和D（1D100），分別表示原野是m*n的矩陣，基德最多只能飛行的距離為D。接下去的m行中，每行包含n個字符，相互之間沒有空格，P表示

55、當前網(wǎng)格是平地，L表示當前網(wǎng)格是湖泊，并且保證(1,1)和(m,n)一定是平地。當m=n=D=0時，表示輸入結(jié)束，程序不應處理這一行。輸出輸出對于每個測試案例，輸出一行，包含一個整數(shù)，為怪盜基德到達基地所需要的最短時間，如果無法到達基地，則輸出impossible。樣例輸入樣例輸入樣例輸出樣例輸出5 5 6PLLLPPPLPPPPLPLLPLPLPLPLP10 10 7PPPLLPPLPPLLLLLLLLLLPPPLLPPLPPLLPLLLLLLLLLPLLLLLLLLLPLLLLLLLPPPPLPPPPPLLLLLLLLLLLLLLLLLLLLPPPLLPPLPP0 0 0207/*/功能：

56、飛躍原野的怪盜基德(優(yōu)先隊列式分支限界法)/作者：鄒競/版本：v1.0/日期：2012-02-22/*/#include #include #include using namespace std;struct Node int x, y; int d; int t; /已耗費時間 operator rhs.t; ;class Flyingprotected: char *map; /地圖 int *mark; /markijk表示到達i,j，剩下飛行長度為k時已經(jīng)耗費的時間 int m, n; int d; int ans; static int dir42; /4個方向 bool InMa

57、p(int x, int y);public: Flying(int mm, int nn, int dd); Flying(); int Search(); void ReadMap(); void Output();int Flying:dir42 = -1, 0, 0, 1, 1, 0, 0, -1;Flying:Flying(int mm, int nn, int dd) m = mm; n = nn; d = dd; map = new char * m; for(int i = 0; i m; i+) mapi = new char n; mark = new int * m; f

58、or(int i = 0; i m; i+) marki = new int * n; for(int j = 0; j n; j+) markij = new int d + 1; Flying:Flying() for(int i = 0; i m; i+) for(int j = 0; j n; j+) delete markij; delete marki; delete mark; for(int i = 0; i = 0 & x = 0 & y n;int Flying:Search() for(int i = 0; i m; i+) for(int j = 0;

59、j n; j+) for(int k = 0; k d + 1; k+) markijk = 0; priority_queue q; Node currNode, nextNode; currNode.x = 0, currNode.y = 0; currNode.d = d; currNode.t = 0; q.push(currNode); markcurrNode.xcurrNode.ycurrNode.d = 1; do if(q.empty() ans = -1; break; currNode = q.top(); q.pop(); if(currNode.x = m - 1 &

60、amp; currNode.y = n - 1) /找到最優(yōu)解 ans = currNode.t; break; /4個方向試探 for(int i = 0; i 4; i+) /如果方向i的下一個位置是平地，則先考慮移動到下一個位置的平地上的情況 nextNode.x = currNode.x + diri0, nextNode.y = currNode.y + diri1; nextNode.d = currNode.d; if(InMap(nextNode.x, nextNode.y) & mapnextNode.xnextNode.y = P & !marknextNode.xnextNode.ynextNode.d) /檢索4個方向的格子是平地的情況 nextNode.t = c