博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 2312Battle City(BFS-priority_queue 或者是建图spfa)
阅读量:5957 次
发布时间:2019-06-19

本文共 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/

你可能感兴趣的文章
SQL Server 查看数据页面
查看>>
js中内建对象
查看>>
strcmp函数和strcpy函数
查看>>
iOS 图形编程总结
查看>>
Vector HashMap List 存取数据速度
查看>>
迪杰斯特拉算法介绍
查看>>
PLSQL_基础系列03_合并操作UNION / UNION ALL / MINUS / INTERSET(案例)
查看>>
ORM是什么?
查看>>
css段落首字母下沉
查看>>
Dynamic CRM 2013学习笔记(二十五)JS调用web service 实现多条记录复制(克隆)功能...
查看>>
Nginx安装配置PHP(FastCGI)环境的教程
查看>>
iPhone开发【一】从HelloWorld開始
查看>>
RAC Concept
查看>>
互斥量和查用户权限
查看>>
puppet master 用 nginx + unicorn 作为前端
查看>>
Sql Server之旅——第六站 使用winHex利器加深理解数据页
查看>>
求CRC校验和的低位和高位的两种方式
查看>>
spark-sql访问hive的问题记录
查看>>
Oracle Cursor的使用
查看>>
SQL Server 2008 (R2) 单机版安装的先决条件
查看>>