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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define N 90010
#define INF 0x3f3f3f3f
using namespace std;
struct node{
   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];
char map[305][305];
int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1};
int ss, tt;
int n, m;
queue<int>q;
bool spfa(){
   q.push(ss);
   memset(vis, 0, sizeof(vis));
   vis[ss]=1;
   memset(d, 0x3f, sizeof(d));
   d[ss]=0;
   while(!q.empty()){
       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;
}

int main(){
   while(cin>>n>>m && (n||m)){
      for(int i=0; i<n; ++i)
        cin>>map[i];
      for(int i=0; i<n; ++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;
}