算法实训(第7学期)-第05周-分支限界法实例(新版,更正了以前的错误)

算法与程序设计实训

(第7学期)

第05周分支限界法实例

（更正了上一版本幻灯片的错误）湖南涉外经济学院信息科学与工程学院邹竞5.1知识回顾1．分支限界法分支限界法是一种广度优先的搜索策略。它在包含问题的所有解的解空间树中，按照广度优先的策略，从根节点出发搜索解空间树，在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有孩子结点。在这些孩子结点中，那些导致不可行解或导致非最优解的孩子结点被舍弃，其余孩子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。2．队列式分支限界法和优先队列式分支限界法从活结点表中选择下一扩展结点的方式通常有以下两种：1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点，因为没有提示信息，所以搜索具有一定的盲目性，效率不高。2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的高低与p值大小相关，根据问题的不同情况，采用大根堆或小根堆来描述优先队列。用一个大根堆来实现最大优先队列，体现最大效益优先的原则；用一个小根堆来实现最小优先队列，体现最小费用优先的原则。曾经学过的例子：单源点最短路径问题、装载问题、纵横布线问题、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）。采用队列式分支限界法，队列元素节点包含当前位置、已经经过的线段数。算法开始时，从第1张牌的位置，沿着上下左右4个方向搜索。由于要求拐弯次数最少，因此，当沿着某个方向搜索时，应该将沿途经过的位置（如果可以有连线经过）的相关信息入队列（也就是换方向以前要将原方向的可以有连线的位置入队列），即当某一个位置的坐标(x,y)依旧在棋盘内，并且该坐标位置没有游戏牌，并且坐标(x,y)以前没有搜索过，则生成相应的节点插入队列，并将坐标(x,y)标记为已访问。随后循环进行如下操作：如果队列元素为空，则说明没有通路，无解，否则从队列当中获取队首节点出队列，如果该节点正好对应第二张游戏牌的坐标，则找到了一个解，否则，按照上下左右4个方向搜索，在改变方向以前将某一方向上可以有连线的位置入队列。反复循环，直到找到解或者确定无解。//作者：邹竞//版本：1.0//日期：2010-07-21#include<iostream>#include<vector>#include<string>#include<queue>usingnamespacestd;structQNode//优先队列节点{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;//找到最优解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在窝中的初始状态，编程求出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的某种状态（Holedox身体所在的网格的坐标，以及蛇头从初始网格到当前网格移动了多少个网格）。引入向量v，存储搜索过的Holedox的状态。将Holedox的初始状态插入队列。然后进行如下循环：如果队列为空，则说明Holedox无法到达出口。否则，将队首元素出队列，如果该元素对应的Holedox身体的蛇头所在的网格就是出口所在的网格，则找到了一个解，否则，对该元素按照上下左右四个方向扩展子节点，如果能到到达某个方向的下一个网格（该网格与当前元素蛇头所在的网格相邻，并且不是该网格不是Holedox身体的一部分，并且该网格没有石头），则让Holedox朝该网格移动，更新Holedox的状态，并生成相应的队列节点插入到队尾。当反复循环，直到找到解或者确定无解。如何记录蛇当前的状态，以避免以后重复的访问变成了关键，在这里我们将蛇的状态描述为如下三元组（x,y,state）,其中(x,y)是蛇头的坐标，state记录的是尾巴的状态，由于尾巴最长为7段，每一段相对于前一段只有上下左右四种状态，仅需要两位表示，则尾巴状态最多需要7×2=14位二进制数表示，则我们可以构建矩阵flag[21][21][16384]来保存访问过的状态，以避免重复访问相同的状态。#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);//求两个节点的相对位置

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)//求两个节点的相对位置{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;}此代码的算法流程正确，但是提交发现超时。超时的原因在于：1、大量的new、delete在堆空间对内存动态分配和回收占用了大量时间；2、STL的queue在时间上没有优势。将程序修改如下：#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)//求两个节点的相对位置{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分析：采用优先队列式分支限界法，队列元素节点信息包含机器人当前位置、机器人面部方向和已经使用的时间，队列元素优先级就是已经使用的时间单位。算法开始时，将机器人的初始信息（包括初始位置、面朝方向、以及已经使用的时间单位0）插入优先队列。随后循环进行如下操作：如果队列元素为空，则说明没有通路，无解，否则从优先队列当中获取优先级最高的节点（已使用时间单位最小的节点）出队列，如果该节点正好对应目的地坐标，则找到了一个解，否则，依次尝试让机器人执行5种命令中的一种，如果该命令可以执行（如没有障碍物阻拦，没有超越边界），并且该状态（包括机器人当前位置、面朝方向）以前没有搜索过，则生成相应的节点插入优先队列，并置该节点对应的状态的搜索标志为已搜索。反复循环，直到找到解或者确定无解。这里，还要解决2个细节问题：（1）机器人的中心总是在格点上，并且只能沿着格点构成的线段移动，并非沿着网格内移动，这样可以看成机器人所在的位置总是在某个网格(i,j)的右下角（0≤i≤n-2,0≤j≤m-2）。（2）机器人的状态不仅包含位置坐标，还应该包含面朝的方向。如果要判断某个状态是否曾经被搜索过，可以引入三维数组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/*******************************///功能：飞跃原野的怪盗基德(优先队列式分支限界法)//作者：邹竞//版本：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