本文共 1969 字,大约阅读时间需要 6 分钟。
/* bfs搜索!要注意的是点与点的权值是不一样的哦! 空地到空地的步数是1, 空地到墙的步数是2(轰一炮+移过去) 所以用到优先队列进行对当前节点步数的更新!*/#include#include #include #include #include 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 , greater >q;bool bfs(){ while(!q.empty()){ node cur=q.top(); q.pop(); if(map[cur.x][cur.y]=='T'){ cout< < >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"< B的权值为1, E->B的权值为2, S<->... R<->... 的权值为INF(也就是没有边存在) 在注意一点就是B->E的权值是 1,因为如果到B了,说明炮弹已经将墙轰掉了! 建立好图之后,那么就是求源点到终点的最短的距离了! 这里采用的spfa算法! */#include #include #include #include #include #include #define N 90010#define INF 0x3f3f3f3fusing namespace std;struct node{ int to; int dist; node(){} node(int to, int dist){ this->to=to; this->dist=dist; }};vector 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 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 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 >map[i]; for(int i=0; i =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"<
转载地址:http://zfgxx.baihongyu.com/