首页 > 代码库 > POJ 2312Battle City(BFS-priority_queue 或者是建图spfa)

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

2024-07-17 10:56:33   220人阅读

 1 /* 2     bfs搜索！要注意的是点与点的权值是不一样的哦！ 3    空地到空地的步数是1， 空地到墙的步数是2（轰一炮+移过去） 4    所以用到优先队列进行对当前节点步数的更新！
       5 */ 6 #include<iostream> 7 #include<queue> 8 #include<cstring> 9 #include<algorithm>10 #include<cstdio>11 using namespace std;12 13 int n, m;14 char map[305][305];15 16 struct node{17     int x, y;18     int step;19     node(){}20     node(int x, int y, int step){21        this->x=x;22        this->y=y;23        this->step=step;24     }25 };26 int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1};27 28 bool operator >(node a, node b){29    return a.step > b.step;30 }31 32 priority_queue<node, vector<node>, greater<node> >q;33 34 bool bfs(){35    while(!q.empty()){36        node cur=q.top();37        q.pop();38        if(map[cur.x][cur.y]==‘T‘){39            cout<<cur.step<<endl;40            return true;41        }42        int xx, yy;43        for(int i=0; i<4; ++i){44            xx=cur.x+dir[i][0];45            yy=cur.y+dir[i][1];46            if(map[xx][yy]==‘R‘ || map[xx][yy]==‘S‘) continue;47            else if(map[xx][yy]==‘T‘){48               cout<<cur.step+1<<endl;49               return true;50            }51            else if(map[xx][yy]==‘B‘)52               q.push(node(xx, yy, cur.step+2)); 53            else54               q.push(node(xx, yy, cur.step+1)); 55            56            map[xx][yy]=‘R‘;57        } 58    }59    return false;60 }61 62 int main(){63     while(cin>>n>>m && (n || m)){64         for(int i=1; i<=n; ++i){65             cin>>(map[i]+1);66             map[i][0]=map[i][m+1]=‘R‘;67             for(int j=1; j<=m; ++j){68                 if(map[i][j]==‘Y‘){69                    q.push(node(i, j, 0));70                    map[i][j]=‘R‘;71                 }72                 map[0][j]=map[n+1][j]=‘R‘;73             }74         }75         if(!bfs())76            cout<<"-1"<<endl;77         while(!q.empty())  q.pop();78      }79     return 0;80 } 
 1 /* 2     将map[i][j]映射到 i*m+j的节点上，建立节点与节点之间的权值的关系！ 3     B->B的权值为1， E->B的权值为2， S<->...  R<->... 的权值为INF（也就是没有边存在）  4     在注意一点就是B->E的权值是 1，因为如果到B了，说明炮弹已经将墙轰掉了！ 5      6     建立好图之后，那么就是求源点到终点的最短的距离了！ 7     这里采用的spfa算法！  8 */ 9 10 #include<iostream>11 #include<cstdio>12 #include<cstring>13 #include<algorithm>14 #include<vector>15 #include<queue>16 #define N 9001017 #define INF 0x3f3f3f3f18 using namespace std;19 struct node{20    int to;21    int dist;22    node(){}23    24    node(int to, int dist){25      this->to=to;26      this->dist=dist;27    }28 };29 vector<node>g[N];30 int vis[N], d[N];31 char map[305][305];32 int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1};33 int ss, tt;34 int n, m;35 queue<int>q;36 bool spfa(){37    q.push(ss);38    memset(vis, 0, sizeof(vis));39    vis[ss]=1;40    memset(d, 0x3f, sizeof(d));41    d[ss]=0;42    while(!q.empty()){43        int u=q.front(); q.pop();44        vis[u]=0;45        int len=g[u].size();46        for(int i=0; i<len; ++i){47            int v=g[u][i].to;48            if(d[v] > d[u] + g[u][i].dist){49                  d[v] = d[u] + g[u][i].dist;50                  51                  if(!vis[v]){52                  q.push(v);53                  vis[v]=1;     54               }55            }56        }57    }58    if(d[tt]==INF)  return false;59    return true;60 }61 62 int main(){63    while(cin>>n>>m && (n||m)){64       for(int i=0; i<n; ++i)65         cin>>map[i];66       for(int i=0; i<n; ++i)67          for(int j=0; j<m; ++j){68              int from=i*m+j;69              if(map[i][j]==‘Y‘)  ss=from;70              else if(map[i][j]==‘T‘) tt=from;71              else if(map[i][j]==‘R‘ || map[i][j]==‘S‘) continue;72              for(int k=0; k<4; ++k){73                  int x=i+dir[k][1];74                  int y=j+dir[k][0];75                  if(x<0 || x>=n || y<0 || y>=m)  continue;76                  if(map[x][y]==‘R‘ || map[x][y]==‘S‘) continue;77                  78                  int to = x*m+y, dist=1;79                  if(map[i][j]==‘B‘ || map[x][y]==‘B‘)  dist=2;80                  if(map[i][j]==‘B‘ && map[x][y]!=‘B‘)  dist=1;81                  g[from].push_back(node(to, dist));82                  83              }84          }85        if(!spfa())86           cout<<"-1"<<endl;87        else cout<<d[tt]<<endl;88        for(int i=0; i<n*m; ++i)89           g[i].clear();90    }91    return 0;92 }

 

 


联系
我们