OpenJudge 6044:鸣人和佐助
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
- 输入
- 输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 - 输出
- 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
- 样例输入
样例输入1
4 4 1
#@##
**##
###+
**** 样例输入2
4 4 2
#@##
**##
###+
****- 样例输出
样例输出1
6 样例输出2
4 什么叫做没有记性呢（哦，刚刚被鉴定过我是没有脑子），就是真的一点印象都没有然后相关的内容一点都不知道。
就是有一种执念要先回忆BFS就是要用BFS写这题，然后就被各种dalao3D环绕版“一般，可行性问题用DFS，最优性问题用BFS。”好的，记住了。
然而这道题只用裸BFS是过不了的。为什么呢？dalao给出一个样例：这样看来，并不能先进先出，元素存在优先级，于是优先队列就出现了。
/*
简单 介绍STL优先队列- 包含头文件：#include<queue.h>
- 简单 常用操作：
q.empty() 如果队列为空，则返回true，否则返回false
q.size() 返回队列中元素的个数
q.pop() 删除队首元素，但不返回其值
q.top() 返回具有最高优先级的元素值，但不删除该元素
q.push(item) 在基于优先级的适当位置插入新元素
- 默认队首为最大元素，若要改变需重载运算符！
（说好的简单）*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std; int t,n,m;
int flag,a=-,b=-,ans=-;
int h[]={,,,-},s[]={,-,,};
char map[][]; struct node{
int u;
int v;
int w;
int c;
friend bool operator < (node a,node b){//重载运算符
if(a.w==b.w)return a.c>b.c ;
else return a.w>b.w;
}
}; priority_queue<node>qu;//定义类型 void BFS(){
node head;
head.u=a;
head.v=b;
head.w=;
head.c=;
qu.push(head);
while(!qu.empty()){
node now=qu.top();//取队首元素
qu.pop();//队首元素弹出
for(int k=;k<;k++){
int U=now.u+h[k];
int V=now.v+s[k];
if(map[U][V]=='+'){
ans=now.w+;
return ;
}
else if(map[U][V]=='*'){
map[U][V]='-';
node neww;
neww.u=U;
neww.v=V;
neww.c=now.c;
neww.w=now.w+;
qu.push(neww);
}
else if(map[U][V]=='#'&&(now.c+)<=t){
map[U][V]='-';
node neww;
neww.c=now.c+;
neww.u=U;
neww.v=V;
neww.w=now.w+;
qu.push(neww);
}
}
}
} int main(){
memset(map,'-',sizeof(map));
scanf("%d%d",&n,&m);
scanf("%d",&t);
for(int i=;i<=n;i++){
scanf("%s",map[i]+);
if(a==-)
for(int j=;j<=m;j++)
if(map[i][j]=='@'){
a=i;
b=j;
}
}
map[a][b]='-';
BFS();
printf("%d\n",ans);
return ;
}