ACM-ICPC 2018北京网络赛-A题 Saving Tang Monk II-优先队列
做法:优先队列模板题,按步数从小到大为优先级,PASS掉曾经以相同氧气瓶走过的地方就好了
题目1 : Saving Tang Monk II
描述
《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace, and he wanted to reach Tang Monk and rescue him.
The palace can be described as a matrix of characters. Different characters stand for different rooms as below:
'S' : The original position of Sun Wukong
'T' : The location of Tang Monk
'.' : An empty room
'#' : A deadly gas room.
'B' : A room with unlimited number of oxygen bottles. Every time Sun Wukong entered a 'B' room from other rooms, he would get an oxygen bottle. But staying there would not get Sun Wukong more oxygen bottles. Sun Wukong could carry at most 5 oxygen bottles at the same time.
'P' : A room with unlimited number of speed-up pills. Every time Sun Wukong entered a 'P' room from other rooms, he would get a speed-up pill. But staying there would not get Sun Wukong more speed-up pills. Sun Wukong could bring unlimited number of speed-up pills with him.
Sun Wukong could move in the palace. For each move, Sun Wukong might go to the adjacent rooms in 4 directions(north, west,south and east). But Sun Wukong couldn't get into a '#' room(deadly gas room) without an oxygen bottle. Entering a '#' room each time would cost Sun Wukong one oxygen bottle.
Each move took Sun Wukong one minute. But if Sun Wukong ate a speed-up pill, he could make next move without spending any time. In other words, each speed-up pill could save Sun Wukong one minute. And if Sun Wukong went into a '#' room, he had to stay there for one extra minute to recover his health.
Since Sun Wukong was an impatient monkey, he wanted to save Tang Monk as soon as possible. Please figure out the minimum time Sun Wukong needed to reach Tang Monk.
输入
There are no more than 25 test cases.
For each case, the first line includes two integers N and M(0 < N,M ≤ 100), meaning that the palace is a N × M matrix.
Then the N×M matrix follows.
The input ends with N = 0 and M = 0.
输出
For each test case, print the minimum time (in minute) Sun Wukong needed to save Tang Monk. If it's impossible for Sun Wukong to complete the mission, print -1
- 样例输入
-
2 2
S#
#T
2 5
SB###
##P#T
4 7
SP.....
P#.....
......#
B...##T
0 0 - 样例输出
-
-1
8
11
#include <iostream>
#include <queue>
#include <cstring>
using namespace std; char mp[][];
bool vis[][][];
int d[][] = { { , },{ -, },{ , },{ ,- } };
int x, y; struct node
{
int x, y;
int step;
int o;
bool operator < (const node &a) const {
return step > a.step;
}
}; int bfs(node st)
{
priority_queue<node> q;
st.step = ;
st.o = ;
q.push(st);
node now, next; while (!q.empty())
{
now = q.top();
q.pop(); for (int i = ; i < ; i++)
{
next = now;
next.step++;
next.x += d[i][];
next.y += d[i][];
if (next.x < || next.y < || next.x >= x || next.y >= y)
continue;
if (next.o == && mp[next.x][next.y] == '#')
continue; if (mp[next.x][next.y] == 'T')
{
return next.step; } if (mp[next.x][next.y] == 'P')
next.step--;
else if (mp[next.x][next.y] == '#')
{
next.step++;
next.o--;
}
else if (mp[next.x][next.y] == 'B')
{
if(next.o < )
next.o++;
} if (vis[next.x][next.y][next.o])
continue; vis[next.x][next.y][next.o] = ;
q.push(next);
}
}
return -;
} int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
while (cin >> x >> y && (x || y))
{
memset(vis, , sizeof(vis));
memset(mp, '.', sizeof(mp));
node st;
for (int i = ; i < x; i++)
for (int j = ; j < y; j++)
{
cin >> mp[i][j];
if (mp[i][j] == 'S')
{
st.x = i;
st.y = j;
}
}
cout << bfs(st) << endl;
} return ;
}
最新文章
- 【腾讯Bugly干货分享】基于RxJava的一种MVP实现
- 疯狂java学习笔记之面向对象(八) - static和final
- Android 通过按钮弹出系统菜单(通过Button显示菜单)转
- OkHttp使用进阶 译自OkHttp Github官方教程
- Android之TextView组件学习
- AngularJS路由跳转
- (转)Python-正则表达式
- Java自己动手写连接池一
- [js高手之路] es6系列教程 - Map详解以及常用api
- 微信公众平台开发,图文回复、access_token生成调用、以及微信SDK的实现(2)
- SSH上一个随笔的基础上添加上hibernate支持
- 洛谷P5108 仰望半月的夜空(后缀数组)
- 3D Slicer Modify Mouse Event 修改3D Slicer中的鼠标响应事件
- mysql---select的五种子句学习(where、group by、having、order by、limit)
- PHP自动加载上——spl_autoload_register
- 【转】ssh服务器启动和客户端常用操作
- [ovs] ovs开启日志debug
- Django 时间与时区设置问题
- MyBatis 注解式开发
- Mac 10.12安装远程桌面工具TeamViewer