POJ 2312Battle City(BFS-priority_queue 或者是建图spfa)

/*

    bfs搜索！要注意的是点与点的权值是不一样的哦！

   空地到空地的步数是1， 空地到墙的步数是2（轰一炮+移过去）

   所以用到优先队列进行对当前节点步数的更新！

*/

#include<iostream>

#include<queue>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

int n, m;

char map[305][305];

struct node{

    int x, y;

    int step;

    node(){}

    node(int x, int y, int step){

       this->x=x;

       this->y=y;

       this->step=step;

    }

};

int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1};

bool operator >(node a, node b){

   return a.step > b.step;

}

priority_queue<node, vector<node>, greater<node> >q;

bool bfs(){

   while(!q.empty()){

       node cur=q.top();

       q.pop();

       if(map[cur.x][cur.y]=='T'){

           cout<<cur.step<<endl;

           return true;

       }

       int xx, yy;

       for(int i=0; i<4; ++i){

           xx=cur.x+dir[i][0];

           yy=cur.y+dir[i][1];

           if(map[xx][yy]=='R' || map[xx][yy]=='S') continue;

           else if(map[xx][yy]=='T'){

              cout<<cur.step+1<<endl;

              return true;

           }

           else if(map[xx][yy]=='B')

              q.push(node(xx, yy, cur.step+2)); 

           else

              q.push(node(xx, yy, cur.step+1)); 

           map[xx][yy]='R';

       } 

   }

   return false;

int main(){

    while(cin>>n>>m && (n || m)){

        for(int i=1; i<=n; ++i){

            cin>>(map[i]+1);

            map[i][0]=map[i][m+1]='R';

            for(int j=1; j<=m; ++j){

                if(map[i][j]=='Y'){

                   q.push(node(i, j, 0));

                   map[i][j]='R';

                }

                map[0][j]=map[n+1][j]='R';

            }

        }

        if(!bfs())

           cout<<"-1"<<endl;

        while(!q.empty())  q.pop();

     }

    return 0;

} 

    将map[i][j]映射到 i*m+j的节点上，建立节点与节点之间的权值的关系！

    B->B的权值为1， E->B的权值为2， S<->...  R<->... 的权值为INF（也就是没有边存在） 

    在注意一点就是B->E的权值是 1，因为如果到B了，说明炮弹已经将墙轰掉了！

    建立好图之后，那么就是求源点到终点的最短的距离了！

    这里采用的spfa算法！ 

#include<vector>

#define N 90010

#define INF 0x3f3f3f3f

   int to;

   int dist;

   node(){}

   node(int to, int dist){

     this->to=to;

     this->dist=dist;

vector<node>g[N];

int vis[N], d[N];

int ss, tt;

queue<int>q;

bool spfa(){

   q.push(ss);

   memset(vis, 0, sizeof(vis));

   vis[ss]=1;

   memset(d, 0x3f, sizeof(d));

   d[ss]=0;

       int u=q.front(); q.pop();

       vis[u]=0;

       int len=g[u].size();

       for(int i=0; i<len; ++i){

           int v=g[u][i].to;

           if(d[v] > d[u] + g[u][i].dist){

                 d[v] = d[u] + g[u][i].dist;

                 if(!vis[v]){

                 q.push(v);

                 vis[v]=1;     

              }

   if(d[tt]==INF)  return false;

   return true;

   while(cin>>n>>m && (n||m)){

      for(int i=0; i<n; ++i)

        cin>>map[i];

         for(int j=0; j<m; ++j){

             int from=i*m+j;

             if(map[i][j]=='Y')  ss=from;

             else if(map[i][j]=='T') tt=from;

             else if(map[i][j]=='R' || map[i][j]=='S') continue;

             for(int k=0; k<4; ++k){

                 int x=i+dir[k][1];

                 int y=j+dir[k][0];

                 if(x<0 || x>=n || y<0 || y>=m)  continue;

                 if(map[x][y]=='R' || map[x][y]=='S') continue;

                 int to = x*m+y, dist=1;

                 if(map[i][j]=='B' || map[x][y]=='B')  dist=2;

                 if(map[i][j]=='B' && map[x][y]!='B')  dist=1;

                 g[from].push_back(node(to, dist));

             }

         }

       if(!spfa())

          cout<<"-1"<<endl;

       else cout<<d[tt]<<endl;

       for(int i=0; i<n*m; ++i)

          g[i].clear();

   return 0;

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3910940.html，如需转载请自行联系原作者