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

算法與程序設計實訓

(第7學期)

第05周分支限界法實例

（更正了上一版本幻燈片的錯誤）湖南涉外經濟學院信息科學與工程學院鄒競5.1知識回顧1．分支限界法分支限界法是一種廣度優(yōu)先的搜索策略。它在包含問題的所有解的解空間樹中，按照廣度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹，在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數值（限界），并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索解空間樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結點所使用的擴展方式不同。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有孩子結點。在這些孩子結點中，那些導致不可行解或導致非最優(yōu)解的孩子結點被舍棄，其余孩子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所求的解或活結點表為空時為止。2．隊列式分支限界法和優(yōu)先隊列式分支限界法從活結點表中選擇下一擴展結點的方式通常有以下兩種：1、隊列式(FIFO)分支限界法：隊列式分支限界法將活結點表組織成一個隊列，并按隊列的先進先出原則選取下一個結點為當前擴展結點，因為沒有提示信息，所以搜索具有一定的盲目性，效率不高。2、優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法將活結點表組織成一個優(yōu)先隊列，交按優(yōu)先隊列中規(guī)定的結點優(yōu)先級選取優(yōu)先級最高的下一個結點成為當前擴展結點。優(yōu)先隊列中規(guī)定的結點優(yōu)先級常用一個與該結點相關的數值p來表示。結點優(yōu)先級的高低與p值大小相關，根據問題的不同情況，采用大根堆或小根堆來描述優(yōu)先隊列。用一個大根堆來實現最大優(yōu)先隊列，體現最大效益優(yōu)先的原則；用一個小根堆來實現最小優(yōu)先隊列，體現最小費用優(yōu)先的原則。曾經學過的例子：單源點最短路徑問題、裝載問題、縱橫布線問題、0-1背包問題、最大團問題、旅行商問題、圓排列問題。5.2實例1：TheGameDescription在一個大小為h行w列（1<=w,h<=75）的矩形棋盤的每一個小方格中，可能放了一張游戲牌也有可能沒放。兩張游戲牌能夠連接起來當且僅當滿足下列條件：（1）從一張游戲牌到另一張游戲牌的連線，由若干水平或垂直線段構成；（2）這些線段中任何一條都不能穿越其他游戲牌，但棋盤邊界外的線段可以不在棋盤內。你的任務是：對于給定的棋盤布局，以及指定的兩張游戲牌，判斷是否存在一條滿足上述條件的線路將他們連接起來，并且若存在這樣的線路，求出需要的線段數最少的線路。例如，圖中第2列第3行的牌，能夠和第5列第3行的牌連接，第1列第3行的牌，能夠和第4列第4行的牌連接，而第3列第2行的牌不能夠和第3列第4行的牌連接。題目來源：/problem?id=1101Input：Theinputcontainsdescriptionsofseveraldifferentgamesituations.Thefirstlineofeachdescriptioncontainstwointegerswandh(1<=w,h<=75),thewidthandtheheightoftheboard.Thenexthlinesdescribethecontentsoftheboard;eachoftheselinescontainsexactlywcharacters:a"X"ifthereisagamepieceatthislocation,andaspaceifthereisnogamepiece.Eachdescriptionisfollowedbyseverallinescontainingfourintegersx1,y1,x2,y2eachsatisfying1<=x1,x2<=w,1<=y1,y2<=h.Thesearethecoordinatesoftwogamepieces.(Theupperleftcornerhasthecoordinates(1,1).)Thesetwogamepieceswillalwaysbedifferent.Thelistofpairsofgamepiecesforaboardwillbeterminatedbyalinecontaining"0000".Theentireinputisterminatedbyatestcasestartingwithw=h=0.Thistestcaseshouldnotbeprocesed.Output：Foreachboard,outputtheline"Board#n:",wherenisthenumberoftheboard.Then,outputonelineforeachpairofgamepiecesassociatedwiththeboarddescription.Eachoftheselineshastostartwith"Pairm:",wheremisthenumberofthepair(startingthecountwith1foreachboard).Followthisby"ksegments.",wherekistheminimumnumberofsegmentsforapathconnectingthetwogamepieces,or"impossible.",ifitisnotpossibletoconnectthetwogamepiecesasdescribedabove.Outputablanklineaftereachboard.SampleInput54XXXXXXXXXXXXXX235313442334000000SampleOutputBoard#1:Pair1:4segments.Pair2:3segments.Pair3:impossible.分析：要求的是最少線段數（也就是拐彎數減1）。采用隊列式分支限界法，隊列元素節(jié)點包含當前位置、已經經過的線段數。算法開始時，從第1張牌的位置，沿著上下左右4個方向搜索。由于要求拐彎次數最少，因此，當沿著某個方向搜索時，應該將沿途經過的位置（如果可以有連線經過）的相關信息入隊列（也就是換方向以前要將原方向的可以有連線的位置入隊列），即當某一個位置的坐標(x,y)依舊在棋盤內，并且該坐標位置沒有游戲牌，并且坐標(x,y)以前沒有搜索過，則生成相應的節(jié)點插入隊列，并將坐標(x,y)標記為已訪問。隨后循環(huán)進行如下操作：如果隊列元素為空，則說明沒有通路，無解，否則從隊列當中獲取隊首節(jié)點出隊列，如果該節(jié)點正好對應第二張游戲牌的坐標，則找到了一個解，否則，按照上下左右4個方向搜索，在改變方向以前將某一方向上可以有連線的位置入隊列。反復循環(huán)，直到找到解或者確定無解。//作者：鄒競//版本：1.0//日期：2010-07-21#include<iostream>#include<vector>#include<string>#include<queue>usingnamespacestd;structQNode//優(yōu)先隊列節(jié)點{intx,y;//當前格子的行、列

intpri;//線段數};classGame{protected:intw,h;//棋盤高度、寬度

char**board;//board[i][j]='W'表示有卡片（障礙物），board[i][j]=''表示沒有卡片

int**grid;//grid[i][j]=0表示第i行第j列還沒有被搜索，grid[i][j]=1表示第i行第j列已經被搜索過

vector<pair<pair<int,int>,pair<int,int>>>v;//保存輸入的兩張卡片的坐標

vector<int>s;//保存結果

staticintdir[4][2];//4個方向public:Game(inthh,intww);~Game();boolInBoard(intx,inty);//判斷i行j列是否在棋盤內

voidReadData();intProcess(intx,inty,intea,inteb);//返回從第x行第y列到第ea行第eb列的最小線段數

voidProcess();voidOutput();};intGame::dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};Game::Game(inthh,intww){w=ww;h=hh;board=newchar*[h+2];for(inti=0;i<h+2;i++)board[i]=newchar[w+2];for(inti=0;i<h+2;i++){for(intj=0;j<w+2;j++)board[i][j]='';}grid=newint*[h+2];for(inti=0;i<h+2;i++)grid[i]=newint[w+2];}Game::~Game(){for(inti=0;i<h+2;i++)delete[]board[i];delete[]board;board=NULL;for(inti=0;i<h+2;i++)delete[]grid[i];delete[]grid;grid=NULL;}boolGame::InBoard(intx,inty){returnx>=0&&x<h+2&&y>=0&&y<w+2;}voidGame::ReadData(){inti=0,j=0,a=0,b=0;pair<pair<int,int>,pair<int,int>>p;v.clear();cin.get();for(i=1;i<=h;i++){cin.getline(board[i]+1,w+1);board[i][w+1]='';}cin>>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;}}intGame::Process(intx,inty,intea,inteb){queue<QNode>q;QNodenewnode,oldnode;for(inti=0;i<h+2;i++){for(intj=0;j<w+2;j++)grid[i][j]=0;}newnode.x=x;newnode.y=y;newnode.pri=0;q.push(newnode);grid[x][y]=1;while(!q.empty()){oldnode=q.front();q.pop();if(oldnode.x==ea&&oldnode.y==eb)returnoldnode.pri;//找到最優(yōu)解for(inti=0;i<4;i++)//4個方向試探

{for(intk=1;;k++){newnode.x=oldnode.x+k*dir[i][0];newnode.y=oldnode.y+k*dir[i][1];newnode.pri=oldnode.pri+1;if(newnode.x==ea&&newnode.y==eb)returnnewnode.pri;if(!InBoard(newnode.x,newnode.y))break;//越界if(grid[newnode.x][newnode.y]==1)break;//好馬不吃回頭草if(board[newnode.x][newnode.y]=='X'&&(newnode.x!=ea||newnode.y!=eb))break;//有障礙

q.push(newnode);grid[newnode.x][newnode.y]=1;}}}return-1;}voidGame::Process(){intiend=v.size();s.clear();for(inti=0;i<iend;i++){intk=Process(v[i].first.first,v[i].first.second,v[i].second.first,v[i].second.second);s.push_back(k);}}voidGame::Output(){intiend=s.size();for(inti=0;i<iend;i++){if(s[i]>-1)cout<<"Pair"<<i+1<<":"<<s[i]<<"segments.\n";elsecout<<"Pair"<<i+1<<":impossible.\n";}}intmain(){intw=0,h=0;intcnt=0;cin>>w>>h;while(h!=0&&w!=0){cnt++;Gameg(h,w);g.ReadData();g.Process();cout<<"Board#"<<cnt<<":\n";g.Output();cout<<"\n";cin>>w>>h;}return0;}5.3實例2：HoledoxMovingHoledox是一種奇怪的蛇，它的窩很像一個迷宮，可以假設其形狀為n*m的矩形網格，每個網格的大小為1*1，窩出口的行列坐標為(1,1)。在每一個網格內，可能有一塊無法移動的石頭，也可能什么也沒有，Holedox就盤踞在窩中若干空白網格內。Holedox身體長度為L，可以用B1(r1,c1)B2(r2,c2)..BL(rL,cL)來表示它的身體,其中Bi和Bi+1

（1<=i<=L-1）處在窩中上下左右相鄰的兩個網格內，B1是它的頭部，BL是它的尾部。當Holedox爬行時，Holedox先選擇一個與其頭部所在網格相鄰的網格，如果這個網格內沒有石頭，且Holedox身體的任何一段都不在這個網格內，則它的頭部就能進入這個網格，同時，Bi進入原先Bi-1所在的網格（2<=i<=L）。Forexample,intheFigure2,atthebeginningthebodyofHoledoxcanberepresentedasB1(4,1)B2(4,2)B3(3,2)B4(3,1).Duringthenextstep,observingthatB1'(5,1)istheonlysquarethattheheadcanbemovedinto,HoledoxmovesitsheadintoB1'(5,1),thenmovesB2intoB1,B3intoB2,andB4intoB3.Thusafteronestep,thebodyofHoledoxlocatesinB1(5,1)B2(4,1)B3(4,2)B4(3,2)(seetheFigure3).你的任務是，給定Holedox窩的描述和Holedox在窩中的初始狀態(tài)，編程求出Holedox的頭部爬行到出口所需要的最少步數。出口在最左上方的那個網格(1,1)。題目來源：/problem?id=1324Input輸入包含多個測試用例。每一個測試用例的第一行包含3個整數n,m(1<=n,m<=20)和L(2<=L<=8)，分別表示矩形洞穴的網格的行數和列數，以及Holedox的身體所占的網格數。接下來又L行數據，表示Holedox身體的每一個網格的位置，順序從B1(r1,c1)到BL(rL,cL)，其中1<=ri<=n,and1<=ci<=m,1<=i<=L。接下來的一行包含一個整數K，表示矩形洞穴的石頭所占的網格數。接下來的K行表示每個石頭所占的網格的行號和列號。然后，以空行分隔每個測試用例，最后一行的000表示測試用例結束。Note:BiisalwaysadjacenttoBi+1(1<=i<=L-1)andexitsquare(1,1)willneverbeastone.OutputForeachtestcaseoutputonelinecontainingthetestcasenumberfollowedbytheminimalnumberofstepsHoledoxhastotake."-1"meansnosolutionforthatcase.SampleInput56441423231323333444423131424421223442000SampleOutputCase1:9Case2:-1分析：采用隊列式分支限界法，隊列元素為當前搜索到的Holedox的某種狀態(tài)（Holedox身體所在的網格的坐標，以及蛇頭從初始網格到當前網格移動了多少個網格）。引入向量v，存儲搜索過的Holedox的狀態(tài)。將Holedox的初始狀態(tài)插入隊列。然后進行如下循環(huán)：如果隊列為空，則說明Holedox無法到達出口。否則，將隊首元素出隊列，如果該元素對應的Holedox身體的蛇頭所在的網格就是出口所在的網格，則找到了一個解，否則，對該元素按照上下左右四個方向擴展子節(jié)點，如果能到到達某個方向的下一個網格（該網格與當前元素蛇頭所在的網格相鄰，并且不是該網格不是Holedox身體的一部分，并且該網格沒有石頭），則讓Holedox朝該網格移動，更新Holedox的狀態(tài)，并生成相應的隊列節(jié)點插入到隊尾。當反復循環(huán)，直到找到解或者確定無解。如何記錄蛇當前的狀態(tài)，以避免以后重復的訪問變成了關鍵，在這里我們將蛇的狀態(tài)描述為如下三元組（x,y,state）,其中(x,y)是蛇頭的坐標，state記錄的是尾巴的狀態(tài)，由于尾巴最長為7段，每一段相對于前一段只有上下左右四種狀態(tài)，僅需要兩位表示，則尾巴狀態(tài)最多需要7×2=14位二進制數表示，則我們可以構建矩陣flag[21][21][16384]來保存訪問過的狀態(tài)，以避免重復訪問相同的狀態(tài)。#include<iostream>#include<queue>#include<cmath>usingnamespacestd;structQNode{ intl; int**snake; intstep; QNode(); QNode(intl); QNode(constQNode&rhs); ~QNode(); QNode&operator=(constQNode&rhs);};QNode::QNode(){l=0;snake=NULL;step=0;}QNode::QNode(intl){ this->l=l;step=0;snake=newint*[l]; for(inti=0;i<l;i++)snake[i]=newint[2];}QNode::~QNode(){for(inti=0;i<l;i++)delete[]snake[i];delete[]snake;}QNode::QNode(constQNode&rhs){ l=rhs.l;step=rhs.step;snake=newint*[l]; for(inti=0;i<l;i++)snake[i]=newint[2]; for(inti=0;i<l;i++) { for(intj=0;j<2;j++)snake[i][j]=rhs.snake[i][j]; }}QNode&QNode::operator=(constQNode&rhs){ l=rhs.l;step=rhs.step;snake=newint*[l]; for(inti=0;i<l;i++)snake[i]=newint[2]; for(inti=0;i<l;i++) { for(intj=0;j<2;j++)snake[i][j]=rhs.snake[i][j]; } return*this;}classHoledoxMoving{protected:intm,n;intl,k;int**map;int**snake;staticintdir[4][2];public:HoledoxMoving(intm,intn,intl);~HoledoxMoving();voidReadData();boolCanArrive(intx,inty,int**snake)const;staticintlocation(intpx,intpy,intnx,intny);//求兩個節(jié)點的相對位置

intGetState(int**snake)const;intBFS();};intHoledoxMoving::dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};HoledoxMoving::HoledoxMoving(intm,intn,intl){this->m=m;this->n=n;this->l=l;map=newint*[m];for(inti=0;i<m;i++)map[i]=newint[n];snake=newint*[l];for(inti=0;i<l;i++)snake[i]=newint[2];}HoledoxMoving::~HoledoxMoving(){for(inti=0;i<m;i++)delete[]map[i];delete[]map;for(inti=0;i<l;i++)delete[]snake[i];delete[]snake;}voidHoledoxMoving::ReadData(){for(inti=0;i<m;i++){for(intj=0;j<n;j++)map[i][j]=0;}for(inti=0;i<l;i++){intr=0,c=0;cin>>r>>c;snake[i][0]=r-1;snake[i][1]=c-1;}cin>>k;for(inti=0;i<k;i++){intr=0,c=0;cin>>r>>c;map[r-1][c-1]=1;}}boolHoledoxMoving::CanArrive(intx,inty,int**snake)const{if(!(x>=0&&x<m&&y>=0&&y<n)||(map[x][y]!=0)){returnfalse;}for(inti=0;i<l;i++){if(x==snake[i][0]&&y==snake[i][1])returnfalse;}returntrue;}intHoledoxMoving::location(intpx,intpy,intnx,intny)//求兩個節(jié)點的相對位置{if(px==nx){if(py>ny)return0;elsereturn1;}else{if(px>nx)return2;elsereturn3;}}intHoledoxMoving::GetState(int**snake)const{ints=0;for(inti=0;i<l-1;i++){s=s*4+location(snake[i][0],snake[i][1],snake[i+1][0],snake[i+1][1]);}returns;}intHoledoxMoving::BFS(){int***flag=newbool**[m];for(inti=0;i<m;i++){flag[i]=newbool*[n];for(intj=0;j<n;j++)flag[i][j]=newbool[1<<(2*(l-1))];}queue<QNode>q;QNodecurrent(l);for(inti=0;i<l;i++){current.snake[i][0]=snake[i][0];current.snake[i][1]=snake[i][1];current.step=0;}intstate=GetState(current.snake);q.push(current);flag[current.snake[0][0]][current.snake[0][1]][state]=true;while(!q.empty()){QNodecurrent=q.front();q.pop();if(current.snake[0][0]==0&¤t.snake[0][1]==0){for(inti=0;i<m;i++){for(intj=0;j<n;j++)delete[]flag[i][j];delete[]flag[i];}delete[]flag;returncurrent.step;}for(inti=0;i<4;i++){intx=current.snake[0][0]+dir[i][0];inty=current.snake[0][1]+dir[i][1];if(!CanArrive(x,y,current.snake))continue;QNodenext(l);for(intj=l-1;j>0;j--){next.snake[j][0]=current.snake[j-1][0];next.snake[j][1]=current.snake[j-1][1];}next.snake[0][0]=x;next.snake[0][1]=y;next.step=current.step+1;intstate=GetState(next.snake);if(flag[x][y][state])continue;q.push(next);flag[x][y][state]=true;}}for(inti=0;i<m;i++){for(intj=0;j<n;j++)delete[]flag[i][j];delete[]flag[i];}delete[]flag;return-1;}intmain(){intCase=1;intm=0,n=0,l=0;cin>>m>>n>>l;while(m>0&&n>0&&l>0){HoledoxMovingobj(m,n,l);obj.ReadData();cout<<"Case"<<Case++<<":"<<obj.BFS()<<"\n";cin>>m>>n>>l;}return0;}此代碼的算法流程正確，但是提交發(fā)現超時。超時的原因在于：1、大量的new、delete在堆空間對內存動態(tài)分配和回收占用了大量時間；2、STL的queue在時間上沒有優(yōu)勢。將程序修改如下：#include<iostream>#include<queue>#include<cmath>usingnamespacestd;structQNode{intl;intsnake[8][2];intstep;};constintdir[4][2]={-1,0,0,1,1,0,0,-1};boolflag[20][20][1<<14];QNodequ[1<<20];voidReadData(intm,intn,intl,intmap[][20],intsnake[][2]){for(inti=0;i<m;i++){for(intj=0;j<n;j++)map[i][j]=0;}for(inti=0;i<l;i++){intr=0,c=0;cin>>r>>c;snake[i][0]=r-1;snake[i][1]=c-1;}intk=0;cin>>k;for(inti=0;i<k;i++){intr=0,c=0;cin>>r>>c;map[r-1][c-1]=1;}}boolCanArrive(intm,intn,intl,intmap[][20],intx,inty,intsnake[][2]){if(!(x>=0&&x<m&&y>=0&&y<n)||(map[x][y]!=0))returnfalse;for(inti=0;i<l;i++){if(x==snake[i][0]&&y==snake[i][1])returnfalse;}returntrue;}intlocation(intpx,intpy,intnx,intny)//求兩個節(jié)點的相對位置{if(px==nx){if(py>ny)return0;elsereturn1;}else{if(px>nx)return2;elsereturn3;}}intGetState(intl,intsnake[][2]){ints=0;for(inti=0;i<l-1;i++){s=s*4+location(snake[i][0],snake[i][1],snake[i+1][0],snake[i+1][1]);}returns;}intBFS(intm,intn,intl,intmap[][20],intsnake[][2]){for(inti=0;i<m;i++){for(intj=0;j<n;j++){for(intk=0;k<1<<(2*(l-1));k++)flag[i][j][k]=false;}}inthead=0,end=0;QNodecurrent;for(inti=0;i<l;i++){current.snake[i][0]=snake[i][0];current.snake[i][1]=snake[i][1];current.step=0;}intstate=GetState(l,current.snake);qu[end++]=current;flag[current.snake[0][0]][current.snake[0][1]][state]=true;while(head<end){QNodecurrent=qu[head++];if(current.snake[0][0]==0&¤t.snake[0][1]==0)returncurrent.step;for(inti=0;i<4;i++){intx=current.snake[0][0]+dir[i][0];inty=current.snake[0][1]+dir[i][1];if(!CanArrive(m,n,l,map,x,y,current.snake))continue;QNodenext;for(intj=l-1;j>0;j--){next.snake[j][0]=current.snake[j-1][0];next.snake[j][1]=current.snake[j-1][1];}next.snake[0][0]=x;next.snake[0][1]=y;next.step=current.step+1;intstate=GetState(l,next.snake);if(flag[x][y][state])continue;qu[end++]=next;flag[x][y][state]=true;}}return-1;}intmain(){intCase=1,m=0,n=0,l=0;intmap[20][20];snake[8][2];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)<<"\n";cin>>m>>n>>l;}return0;}5.4實例3：ROBOTDescriptionRMI現在正嘗試用機器人搬運物品。機器人的形狀是一個直徑1.6米的球。在試驗階段，機器人被用于在一個儲藏室中搬運貨物。儲藏室是一個N*M的網格，有些格子為不可移動的障礙。機器人的中心總是在格點上，機器人必須在最短的時間內把物品搬運到指定的地方。機器人接受的指令有：1、向前移動1步（Creep）；2、向前移動2步（Walk）；3、向前移動3步（Run）；4、向左轉（Left）；5、向右轉（Right）。

每個指令所需要的時間為1秒。請你計算一下機器人完成任務所需的最少時間。題目來源：/problem?id=1376Input輸入的第一行為兩個正整數N,M（N,M<=50），下面N行是儲藏室的構造，0表示無障礙，1表示有障礙，數字之間用一個空格隔開。接著一行有四個整數和一個大寫字母，分別為起始點和目標點左上角網格的行與列，起始時的面對方向（東E，南S，西W，北N），數與數，數與字母之間均用一個空格隔開。終點的面向方向是任意的。Output輸出整數，表示機器人完成任務所需的最少時間。如果無法到達，輸出-1。SampleInput9100000001000000000001000010000000010000000000000100000000100000001100000000000000010000000107227south00SampleOutput12分析：采用優(yōu)先隊列式分支限界法，隊列元素節(jié)點信息包含機器人當前位置、機器人面部方向和已經使用的時間，隊列元素優(yōu)先級就是已經使用的時間單位。算法開始時，將機器人的初始信息（包括初始位置、面朝方向、以及已經使用的時間單位0）插入優(yōu)先隊列。隨后循環(huán)進行如下操作：如果隊列元素為空，則說明沒有通路，無解，否則從優(yōu)先隊列當中獲取優(yōu)先級最高的節(jié)點（已使用時間單位最小的節(jié)點）出隊列，如果該節(jié)點正好對應目的地坐標，則找到了一個解，否則，依次嘗試讓機器人執(zhí)行5種命令中的一種，如果該命令可以執(zhí)行（如沒有障礙物阻攔，沒有超越邊界），并且該狀態(tài)（包括機器人當前位置、面朝方向）以前沒有搜索過，則生成相應的節(jié)點插入優(yōu)先隊列，并置該節(jié)點對應的狀態(tài)的搜索標志為已搜索。反復循環(huán)，直到找到解或者確定無解。這里，還要解決2個細節(jié)問題：（1）機器人的中心總是在格點上，并且只能沿著格點構成的線段移動，并非沿著網格內移動，這樣可以看成機器人所在的位置總是在某個網格(i,j)的右下角（0≤i≤n-2,0≤j≤m-2）。（2）機器人的狀態(tài)不僅包含位置坐標，還應該包含面朝的方向。如果要判斷某個狀態(tài)是否曾經被搜索過，可以引入三維數組state，state[i][j][k]表示坐標(i,j)，機器人面朝方向k是否已經被搜索過。#include<iostream>#include<algorithm>#include<queue>#include<string>usingnamespacestd;structQNode{intx,y;intf;intt;booloperator<(constQNode&rhs)const;};boolQNode::operator<(constQNode&rhs)const{returnt>rhs.t;}classPoj1376{protected:intm,n;int**maze;bool***state;intendx,endy;//終點

QNoderobot;staticintdir[4][2];public:Poj1376(intmm,intnn);~Poj1376();voidReadData();intBFS();};intPoj1376::dir[4][2]={-1,0,0,1,1,0,0,-1};//上右下左Poj1376::Poj1376(intmm,intnn){m=mm;n=nn;maze=newint*[m];for(inti=0;i<m;i++)maze[i]=newint[n];state=newbool**[m];for(inti=0;i<m;i++){state[i]=newbool*[n];for(intj=0;j<n;j++)state[i][j]=newbool[4];}}Poj1376::~Poj1376(){for(inti=0;i<m;i++){for(intj=0;j<n;j++)delete[]state[i][j];delete[]state[i];}delete[]state;for(inti=0;i<m;i++)[]maze[i];delete[]maze;}voidPoj1376::ReadData(){for(inti=0;i<m;i++){for(intj=0;j<n;j++)cin>>maze[i][j];}intx=0,y=0;cin>>x>>y;robot.x=x-1;robot.y=y-1;cin>>x>>y;endx=x-1;endy=y-1;stringch;cin>>ch;switch(ch[0]){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;}intPoj1376::BFS(){priority_queue<QNode>q;for(inti=0;i<m;i++){for(intj=0;j<n;j++){for(intk=0;k<4;k++)state[i][j][k]=0;}}q.push(robot);state[robot.x][robot.y][robot.f]=1;while(!q.empty()){QNodecurrent=q.top();q.pop();if(current.x==endx&¤t.y==endy)returncurrent.t;QNodenext=current;for(intk=1;k<=3;k++){next.x=current.x+k*dir[current.f][0];next.y=current.y+k*dir[current.f][1];next.f=current.f;next.t=current.t+1;if(next.x<0||next.x>=m-1||next.y<0||next.y>=n-1){break;}boolflag=false;for(inti=min(current.x,next.x);i<=max(current.x,next.x);i++){for(intj=min(current.y,next.y);j<=max(current.y,next.y);j++){if(maze[i][j]==1||maze[i+1][j]==1||maze[i][j+1]==1||maze[i+1][j+1]==1){flag=true;break;}}if(flag)break;}if(flag)break;if(state[next.x][next.y][next.f]==0){q.push(next);state[next.x][next.y][next.f]=1;}}next=current;next.f--;if(next.f<0)next.f=4+next.f;next.t++;if(state[next.x][next.y][next.f]==0){q.push(next);state[next.x][next.y][next.f]=1;}next=current;next.f=(next.f+1)%4;next.t++;if(state[next.x][next.y][next.f]==0){q.push(next);state[next.x][next.y][next.f]=1;}}return-1;}intmain(){intm=0,n=0;cin>>m>>n;while(m>0&&n>0){Poj1376obj(m,n);obj.ReadData();cout<<obj.BFS()<<"\n";cin>>m>>n;}return0;}飛躍原野的怪盜基德怪盜基德成功盜取了寶石，正在向自己的基地撤退。但由于后面有著一群追兵，在名偵探毛利小五郎和中村警部的率領下窮追不舍。所以基德要盡快地返回基地，否則就會被對手逮住。終于基德來到了最后的一站：關東原野，穿過這里就可以回到基地了。然而敵人依然緊追不舍。不過，關東的地理條件對基德十分有利，眾多的湖泊隨處分布。對手需要繞道而行，但基德擁有神奇的滑翔翼，使得它能輕松快速的飛越湖面。當然，為了保證安全起見，基德還是決定找一條能最快回到基地的路。假設關東原野是一個m*n矩陣，它有兩種地，P表示平地，L表示湖泊。基德只能停留在平地上，他目前的位置在左上角(1,1)處，而目的地為右下角的(m,n)，基德可以向前后左右4個方向移動或者飛行，每移動1格需要1單位時間，而飛行的時間主要花費在變形上，飛行本身時間消耗很短，所以無論一次飛行多遠的距離，都只需要1單位時間。飛行的途中不能變向，并且一次飛行最終必須要降落在平地上。由于滑翔翼受到能量的限制，基德不能無限制的飛行，他總共最多可以飛行的距離為D。在知道了以上的信息后，請你幫助基德計算一下，他最快到達基地所需要的時間。輸入輸入包含多個測試案例。每個測試案例的開頭一行是3個非負整數m（1≤m≤100）、n（1≤n≤100）和D（1≤D≤100），分別表示原野是m*n的矩陣，基德最多只能飛行的距離為D。接下去的m行中，每行包含n個字符，相互之間沒有空格，P表示當前網格是平地，L表示當前網格是湖泊，并且保證(1,1)和(m,n)一定是平地。當m=n=D=0時，表示輸入結束，程序不應處理這一行。輸出對于每個測試案例，輸出一行，包含一個整數，為怪盜基德到達基地所需要的最短時間，如果無法到達基地，則輸出impossible。樣例輸入樣例輸出556PLLLPPPLPPPPLPLLPLPLPLPLP10107PPPLLPPLPPLLLLLLLLLLPPPLLPPLPPLLPLLLLLLLLLPLLLLLLLLLPLLLLLLLPPPPLPPPPPLLLLLLLLLLLLLLLLLLLLPPPLLPPLPP000207/*******************************///功能：飛躍原野的怪盜基德(優(yōu)先隊列式分支限界法)//作者：鄒競//版本：v1.0//日期：2012-02-22/*******************************/#include<iostream>#include<fstream>#include<queue>usingnamespacestd;structNode{intx,y;intd;intt;//已耗費時間

operator<(constNode&rhs)const{returnt>rhs.t;}};classFlying{protected:char**map;//地圖

int***mark;//mark[i][j][k]表示到達[i,j]，剩下飛行長度為k時已經耗費的時間

intm,n;intd;intans;staticintdir[4][2];//4個方向

boolInMap(intx,inty);public:Flying(intmm,intnn,intdd);~Flying();intSearch();voidReadMap();voidOutput();};intFlying::dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};Flying::Flying(intmm,intnn,intdd){m=mm;n=nn;d=dd;map=newchar*[m];for(inti=0;i<m;i++){map[i]=newchar[n];}mark=newint**[m];for(inti=0;i<m;i++){mark[i]=newint*[n];for(intj=0;j<n;j++){mark[i][j]=newint[d+1];}}}Flying::~Flying(){for(inti=0;i<m;i++){for(intj=0;j<n;j++)delete[]mark[i][j];delete[]mark[i];}delete[]mark;for(inti=0;i<m;i++)delete[]map[i];delete[]map;}boolFlying::InMap(intx,inty){returnx>=0&&x<m&&y>=0&&y<n;}intFlying::Search(){for(inti=0;i<m;i++){for(intj=0;j<n;j++){for(intk=0;k<d+1;k++)mark[i][j][k]=0;}}priority_queue<Node>q;NodecurrNode,nextNode;currNode.x=0,currNode.y=0;currNode.d=d;currNode.t=0;q.push(currNode);mark[currNode.x][currNode.y][currNode.d]=1;do