HDU——1242Rescue(BFS+优先队列求点图最短路)
Rescue
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25203 Accepted Submission(s): 8936
Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up,
down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.
You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.
Process to the end of the file.
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
自从懂了点BFS,这些就都是水过了。
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
typedef long long LL;
const double PI=acos(-1.0);
const int N=205;
char pos[N][N];
int vis[N][N];
int n,m;
struct info
{
int x;
int y;
int time;
bool operator<(const info &b)const
{
return time>b.time;
}
};
inline info operator+(const info &a,const info &b)
{
info c;
c.x=a.x+b.x;
c.y=a.y+b.y;
return c;
}
info direct[4]={{1,0,0},{0,1,0},{-1,0,0},{0,-1,0}};
info S;
priority_queue<info>Q;
void init()
{
MM(pos);
MM(vis);
while (!Q.empty())
Q.pop();
}
bool check(const info &a)
{
return (a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&!vis[a.x][a.y]&&pos[a.x][a.y]!='#');
}
int main(void)
{
int i,j;
while (~scanf("%d%d",&n,&m))
{
init();
for (i=0; i<n; i++)
{
for (j=0; j<m; j++)
{
cin>>pos[i][j];
if(pos[i][j]=='a')
{
S.x=i;
S.y=j;
}
}
}
int r=-1;
S.time=0;
vis[S.x][S.y]=1;
Q.push(S);
while (!Q.empty())
{
info now=Q.top();
Q.pop();
if(pos[now.x][now.y]=='r')
{
r=now.time;
break;
}
for (i=0; i<4; i++)
{
info v=now+direct[i];
if(check(v))
{
v.time=now.time+(pos[v.x][v.y]=='x'?2:1);
vis[v.x][v.y]=1;
Q.push(v);
}
}
}
r==-1?puts("Poor ANGEL has to stay in the prison all his life."):printf("%d\n",r);
}
return 0;
}
最新文章
- 动画的使用&mdash;Drawable Animation
- 读书笔记:const和readonly、static readonly 那些事
- 浅谈Excel开发:三 Excel 对象模型
- 一键搞定JavaEE应用,JRE+Tomcat+Mysql-JaveEE绿色运行环境JTM0.9版
- duilib进阶教程 -- 改进List控件 (16)
- 介绍UDF,以及完成大小写的转换
- 由浅入深了解Thrift之客户端连接池化
- JSONModel的基本使用
- oldboy第五天学习
- 常见ActiveX控件下载大全
- android studio导入矢量svg图标技巧
- SSH网上商城---商品详情页的制作
- luogu 1731 搜索剪枝好题
- freemarker知识点
- centos7通过yum安装mysql8
- Centos7 出现Welcome to emergency mode!
- 基于TensorFlow Object Detection API进行相关开发的步骤
- 【Linux】【Chrome】安装Chrome浏览器的攻略
- 烦人的IE7、8,半透明滤镜(filter:alpha)失效、png半透明失效的解决办法
- celery简单理解和使用