当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3887:The Pharaoh's Curse

题目描述
Most of the contestants managed to arrive at the Benelux Algorithm Programming Contest on time. All except those unfortunate souls who chose to use a cheap car navigation system. A couple of wrong turns led them completely off course, and now they have ended up all over the world.
Consider the case of contestant J.-P. B. (who has asked to remain anonymous). After driving for countless hours he found himself beneath three miles of water in the middle of the Atlantic Ocean. He was so focused on his navigation system that he failed to look outside until he noticed that the air was getting very moist. Fortunately for this contestant there was a spare submarine under his seat, which allowed him to escape this perilous situation.
Tragic as this story seems, it is not even the worst. Another contestant, whom we will simply call S, wisely decided to travel by train. Sadly, she still listened to the advice of her evil car navigation system, and this morning she took a southbound train instead of heading north. After some more bad directions she found herself locked inside a labyrinth, in the pyramid of the Egyptian pharaoh Sok-O-Ban. As any experienced adventurer knows, these ancient tombs
are often riddled with traps and other mechanisms. Sok-O-Ban's final resting place was no exception.
During his lifetime this pharaoh was known for his sadistic behavior, and he liked to give impossible challenges to random strangers. It is therefore no coincidence that the cavern where contestant S ended up was completely closed off, surrounded by solid rock on every side.
After looking around, our protagonist S managed to draw a map of the tomb. Fortunately she found no skeletons, mummies or spiked death traps. She did discover some buttons embedded in the floor tiles. If she could press them all at the same time, then the hidden exit would open. But as soon as she would release one of the buttons, the door would close again.
Besides the buttons, the walls and a few dusty floor tiles, there were also two sarcophagi filled with rocks. To accommodate the small stature of the ancient Egyptians, the sarcophagi were cubes with sides measuring 1 meter, the same size as the floor tiles. It seemed that these sarcophagi were the key to escaping: by pushing them onto the buttons the exit could be kept open. Only one small problem remained: the sarcophagi were far too heavy to move by hand and too large to climb over.
Fortunately for S, the pharaoh did not anticipate the portable sarcophagus transporter she had conveniently stashed in her backpack. Attaching this reusable system to her arms allowed her to effortlessly push a sarcophagus exactly one meter straight ahead. This corresponds nicely to the 1 meter steps S used when marking out the grid in her map.
输入解释
On the first line of the input is a positive integer, the number of test cases. Then for each test case:
A line containing two positive integers h,w <= 50, the height and width of the maze.
h lines of w characters each, the map of the cavern our protagonist made, in which:
- '#' is a wall or otherwise impassible space.
- '.' is an empty space, of which there are at most 100.
- 'S' is our protagonist.
- 'X' is one of the heavy sarcophagi. There are at most two of these.
- 'B' is a button.
- 'E' is the exit. There is exactly one exit, on the edge of the map.
The edge of the map contains only walls and the exit.
输出解释
For each test case:
One line containing the minimum number of steps (S always takes one meter steps along the grid lines, possibly pushing a sarcophagus.) it will take S to escape the tomb, or the text "impossible" if she cannot escape.
输入样例
3
7 8
########
#..S...#
#.####.#
#.#.XB.#
#.####.#
#......E
########
7 8
########
#..S...#
#.####.#
#.#.BX.#
#.####.#
#......E
########
4 8
##E#####
#...####
#SX.XBB#
########
输出样例
impossible
10
19

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 BAPC 2009

源链接: POJ-3887

最后修改于 2020-10-29T07:14:41+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536