快捷導航

深入探討POJ 2312 Battle City 優(yōu)先隊列+BFS

更新時間：2013年05月23日 17:33:38 作者：

本篇文章是對優(yōu)先隊列+BFS進行了詳細的分析介紹，需要的朋友參考下

相信坦克大戰(zhàn)大家都玩過吧，本題就是根據(jù)這個游戲設(shè)計的。坦克要從起點（Y），到目的地（T），坦克不能通過鋼墻（S），河（R），可以在空地在行走（E），射擊破壞磚墻（B），射擊磚墻時不行走且花費一個單位的時間，在空地上行走時也花費一個單位的時間。求坦克從起點到目的地最少花多少時間，不可達輸出－1；
很好的一道搜索題。因為考慮到通過磚墻時和空地所花的時間不同，所以不能使用一般的BFS廣搜來做。用DFS深搜，你會發(fā)現(xiàn)時間復(fù)雜非常高，必然會超時（最大是300＊300的圖）。本題可以使用改進過的廣搜或優(yōu)先隊列＋bfs 或記憶化廣搜三種方法來解決。
第一種方法：改進過的BFS：
有些節(jié)點需要耗費2個單位時間，要想用BFS就得改一下，由于BFS每次只能操作一步，要不就是擴展，要不就是破壞磚墻。所以只需檢查該點是不是'B'，是的話就得停一步，不是的話，繼續(xù)擴展，也就是說某些點的擴展慢了一拍，所以從隊列里出來的點就判斷一下再看執(zhí)行哪個操作。
從這道題，我也對bfs有了更深的理解，“bfs之所以能最快找到最優(yōu)解，就是因為它每次操作一步（這里的操作一步，很靈活，例如題目中的破壞磚墻），而while（）里面的語句就是一次操作了！”

復(fù)制代碼代碼如下:

/*
這道題中B點需要操作兩步，所以遇到B點后不能+2后直接壓進隊列，需要在原地停一下，不能擴展到其他點，相當于他只能擴展到自身，所以就把自身壓進隊列里map[x][y]='E'是因為破壞磚墻一次就夠了，不然下次，還是'B'，不斷壓進隊列，不斷在原地停留
平常一般是考慮“入隊列” 的點，這次要考慮“出隊列” 的點是否滿足條件！
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
 int x,y,time;
};
int bfs()
{
 int i;
 node you,start,next;
 queue<node>q;
 you.x=sx;
 you.y=sy;
 you.time=0;
 q.push(you);
 visit[sx][sy]=1;
 while(!q.empty())
 {
  start=q.front();
  q.pop();
  if(map[start.x][start.y]=='B')  //這一步需要停一停
  {
   start.time++;
   map[start.x][start.y]='E';
   q.push(start);
  }
  else
  {
   for(i=0;i<4;i++)
   {
    next.x=start.x+dir[i][0];     //搜索下一個點
    next.y=start.y+dir[i][1];
    if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y])        //判斷下一個點是否合法
     continue;
    next.time=start.time+1;
    if(map[next.x][next.y]=='T')    //到達目的地
     return next.time;
    visit[next.x][next.y]=1;   //標記已經(jīng)走過的點
    q.push(next);
   }
  }
 }
 return -1;
}
int main(void)
{
 int i,j;
 while(scanf("%d %d",&m,&n)==2)
 {
  if(m==0 && n==0)
   break;
  memset(visit,0,sizeof(visit));     //初始化每個節(jié)點的狀態(tài)
  for(i=0;i<m;i++)
  {
   getchar();
   for(j=0;j<n;j++)
   {
    scanf("%c",&map[i][j]);
    if(map[i][j]=='Y')      //記錄起始點
    {
     sx=i;
     sy=j;
    }
   }
  }
  printf("%d\n",bfs());
 }
 system("pause");
 return 0;
}

第二種方法：優(yōu)先隊列＋BFS法
也是用到了廣搜的思想，只是在出隊時做了處理，利用優(yōu)先隊列讓隊列中到起點的時間值最小的點先出隊。該方法會用到優(yōu)先隊列的STL。
首先需要了解優(yōu)先隊列的使用規(guī)則：
優(yōu)先隊列中元素的比較規(guī)則默認是按元素的值從大到小排序的，就是說隊列中最大的元素總是位于隊首，所以出隊時，并非按先進先出的原則進行，而是將當前隊列中最大的元素出隊。這點類似于給隊列里的元素進行了從大到小的排序。當然，可以通過重載“<”操作符來重新定義比較規(guī)則。
重載“<”操作符的函數(shù)可以寫在結(jié)構(gòu)體里面，也可以寫在結(jié)構(gòu)體外面，寫在結(jié)構(gòu)體外面的時候，記得函數(shù)的參數(shù)要使用引用。。
第一種重載方法：

復(fù)制代碼代碼如下:

struct node
{
 int x,y;
 int step;
};
priority_queue<node>q;       //優(yōu)先隊列中元素的比較規(guī)則默認是按元素的值從大到小排序；
bool operator<(const node &a,const node &b) //括號里面是const 而且還必須是引用
{
 return a.step>b.step;          //從小到大排序。重載小于號。因為默認是從大到小
}

第二種重載方法：

復(fù)制代碼代碼如下:

struct node
{
 int x,y;
 int time;  //定義一個優(yōu)先隊列
 friend bool operator<(node a, node b)
 {     //從小到大排序采用“>”號；如果要從大到小排序，則采用“<”號
  return a.time> b.time;       //從小到大排序
 }
};  
priority_queue<node>q;       //優(yōu)先隊列中元素的比較規(guī)則默認是按元素的值從大到小排序；

切記：從小到大排序采用“>”號；如果要從大到小排序，則采用“<”號；

復(fù)制代碼代碼如下:

/*
優(yōu)先隊列的實現(xiàn)就不用局限每次操作一步了，但每次都取最小操作次數(shù)的步來走
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
 int x,y,time;  //定義一個優(yōu)先隊列
 friend bool operator<(node a, node b)
 {
  return a.time> b.time;       //從小到大排序
 }
};
int bfs()
{
 int i;
 node you,start,next;
 priority_queue<node>q;
 you.x=sx;
 you.y=sy;
 you.time=0;
 q.push(you);
 visit[sx][sy]=1;
 while(!q.empty())
 {
  start=q.top();  //取隊頭指針與普通隊列不同（Q.front）
  q.pop();
  for(i=0;i<4;i++)
  {
   next.x=start.x+dir[i][0];     //搜索下一個點
   next.y=start.y+dir[i][1];
   if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y])        //判斷下一個點是否合法
    continue;
   if(map[next.x][next.y]=='B')  //注意此處不要馬虎
    next.time=start.time+2;
   else
    next.time=start.time+1;
   if(map[next.x][next.y]=='T')    //到達目的地
    return next.time;
   visit[next.x][next.y]=1;        //標記已經(jīng)走過的點
   q.push(next);
  }
 }
 return -1;
}
int main(void)
{
 int i,j;
 while(scanf("%d %d",&m,&n)==2)
 {
  if(m==0 && n==0)
   break;
  memset(visit,0,sizeof(visit));     //初始化每個節(jié)點的狀態(tài)
  for(i=0;i<m;i++)
  {
   getchar();
   for(j=0;j<n;j++)
   {
    scanf("%c",&map[i][j]);
    if(map[i][j]=='Y')      //記錄起始點
    {
     sx=i;
     sy=j;
    }
   }
  }
  printf("%d\n",bfs());
 }
 system("pause");
 return 0;
}

第三種方法：記憶化廣搜
和優(yōu)先隊列BFS在出隊時做處理不同的是，記憶化廣搜是在點入隊是做處理。記憶化廣搜時不必要對點進行標記，只是在入隊是注意選擇。比如若搜到A點時，要選擇比A點時間值大的鄰接點入隊（不能相等），并更新入隊點的時間值。

復(fù)制代碼代碼如下:

#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
int co,ro,mi,step[305][305];
char map[305][305],visited[305][305];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
typedef struct node
{
 int x;
 int y;
 int time;
}node;
bool judge(int x,int y)
{
 if(x<0||y<0||x>=co||y>=ro)
 {
  return false;
 }
 if(map[x][y]=='S'||map[x][y]=='R')
 {
  return false;
 }
 return true;
}
void  bfs(int a,int b)
{
 int i,x,y,ti;
 node in,out;
 queue<node>que;
 in.x=a;
 in.y=b;
 step[a][b]=0;
 que.push(in);
 while(!que.empty())
 {
  out=que.front();
  que.pop();
  visited[out.x][out.y]=0;   
  for(i=0;i<4;i++)
  {
   x=out.x+dir[i][0];
   y=out.y+dir[i][1];
   if(!judge(x,y))
    continue;
   ti=step[out.x][out.y]+1;
   if(map[x][y]=='B')
    ti++;
   if(step[x][y]<=ti)
    continue;
   step[x][y]=ti;
   if(visited[x][y])
    continue;
   visited[x][y]=1;
   in.x=x;
   in.y=y;
   que.push(in);
  }
 }
}
int main()
{
 int i,j,a,b,c,d;
 while(scanf("%d %d",&co,&ro),co+ro)
 {
  getchar();
  for(i=0;i<co;i++)
   gets(map[i]);
  for(i=0;i<co;i++)
   for(j=0;j<ro;j++)
   {
    if(map[i][j]=='Y')
    {
     a=i;
     b=j;
    }
    if(map[i][j]=='T')
    {
     c=i;
     d=j;
    }
    step[i][j]=999999;       
   }
   memset(visited,0,sizeof(visited));
   visited[a][b]=1;
   bfs(a,b);
   if(step[c][d]!=999999)
    printf("%d\n",step[c][d]);
   else
    printf("-1\n");
 }
 return 0;
}