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

 /*
bfs搜索!要注意的是点与点的权值是不一样的哦!
空地到空地的步数是1, 空地到墙的步数是2(轰一炮+移过去)
所以用到优先队列进行对当前节点步数的更新!
POJ 2312Battle City(BFS-priority_queue 或者是建图spfa)
*/
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std; int n, m;
char map[][]; 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[][]={, , , , -, , , -}; 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=; i<; ++i){
xx=cur.x+dir[i][];
yy=cur.y+dir[i][];
if(map[xx][yy]=='R' || map[xx][yy]=='S') continue;
else if(map[xx][yy]=='T'){
cout<<cur.step+<<endl;
return true;
}
else if(map[xx][yy]=='B')
q.push(node(xx, yy, cur.step+));
else
q.push(node(xx, yy, cur.step+)); map[xx][yy]='R';
}
}
return false;
} int main(){
while(cin>>n>>m && (n || m)){
for(int i=; i<=n; ++i){
cin>>(map[i]+);
map[i][]=map[i][m+]='R';
for(int j=; j<=m; ++j){
if(map[i][j]=='Y'){
q.push(node(i, j, ));
map[i][j]='R';
}
map[][j]=map[n+][j]='R';
}
}
if(!bfs())
cout<<"-1"<<endl;
while(!q.empty()) q.pop();
}
return ;
}
 /*
将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[][];
int dir[][]={, , , , -, , , -};
int ss, tt;
int n, m;
queue<int>q;
bool spfa(){
q.push(ss);
memset(vis, , sizeof(vis));
vis[ss]=;
memset(d, 0x3f, sizeof(d));
d[ss]=;
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=;
int len=g[u].size();
for(int i=; 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]=;
}
}
}
}
if(d[tt]==INF) return false;
return true;
} int main(){
while(cin>>n>>m && (n||m)){
for(int i=; i<n; ++i)
cin>>map[i];
for(int i=; i<n; ++i)
for(int j=; 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=; k<; ++k){
int x=i+dir[k][];
int y=j+dir[k][];
if(x< || x>=n || y< || y>=m) continue;
if(map[x][y]=='R' || map[x][y]=='S') continue; int to = x*m+y, dist=;
if(map[i][j]=='B' || map[x][y]=='B') dist=;
if(map[i][j]=='B' && map[x][y]!='B') dist=;
g[from].push_back(node(to, dist)); }
}
if(!spfa())
cout<<"-1"<<endl;
else cout<<d[tt]<<endl;
for(int i=; i<n*m; ++i)
g[i].clear();
}
return ;
}
上一篇:MySQL数据库主键设计原则


下一篇:core里使用log4net