当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
5010：Get the Nut
题目描述
Squirrely has lost his lifetime collection of acorns in an unfortunate geyser accident and now he needs your help! Roll the animals around and get Squirrely to the Acorn, but beware! Not all animals are fluffy as they appear to be. Start from your home forest, and continue through the harsh weather of the snow, the scary swamp and the vast wild west! In your journey you will encounter great dangers, but don’t worry! You and Squirrely will be a great team.
Get the Nut is a very cute game as mentioned above. Now Squirrely is in a forest, which can be divided into 6 rows and 8 columns, 48 grids in total. Squirrely wants to get the nut in another grid. However, it is much more difficult than you can image because the forest is full of danger. There are two kinds of other animal in the forest: Mouse and Pig. Pigs are very vicious, they will kill and eat any other animal (except Pigs, of course) in the adjacent grids. Here “adjacent” means two grids share a common edge. Once any other animal enter grids adjacent to a Pig, it will stop and be eaten. Once an animal is adjacent to the nut, it will stop and eat the nut. So if Squirrely is eaten by a Pig or the nut is eaten by a Pig or a Mouse, the game is over and you fail. At the beginning of the game, each animal occupies one grid. For each step, you can choose one animal to roll in either up, down, left or right direction, the animal will keep rolling until it reach the border of the forest or hit a tree or an animal. Your task is to calculate the minimal number of steps should be made that Squirrely can get the nut.
Get the Nut is a very cute game as mentioned above. Now Squirrely is in a forest, which can be divided into 6 rows and 8 columns, 48 grids in total. Squirrely wants to get the nut in another grid. However, it is much more difficult than you can image because the forest is full of danger. There are two kinds of other animal in the forest: Mouse and Pig. Pigs are very vicious, they will kill and eat any other animal (except Pigs, of course) in the adjacent grids. Here “adjacent” means two grids share a common edge. Once any other animal enter grids adjacent to a Pig, it will stop and be eaten. Once an animal is adjacent to the nut, it will stop and eat the nut. So if Squirrely is eaten by a Pig or the nut is eaten by a Pig or a Mouse, the game is over and you fail. At the beginning of the game, each animal occupies one grid. For each step, you can choose one animal to roll in either up, down, left or right direction, the animal will keep rolling until it reach the border of the forest or hit a tree or an animal. Your task is to calculate the minimal number of steps should be made that Squirrely can get the nut.
输入解释
There are multiple test cases. Please process till EOF.
Each test case gives the map of the forest, which has 6 rows and 8 columns. Each grid of the map is one of the following six characters:
1. '.' - the empty area which every animal can stay or go through
2. '#' - the tree which is an obstacle
3. 'S' - the Squirrely
4. 'M' - a Mouse
5. 'P' - a Pig
6. 'N' - the nut which the Squirrely want to get
You should notice that there is one blank line before every test case. You may assume that there is one and only one nut in the forest and the number of animals in the forest will not exceed 5, and the input guarantees that there are at most 32 empty grids(including the original grids occupied by animals) in the map.
Each test case gives the map of the forest, which has 6 rows and 8 columns. Each grid of the map is one of the following six characters:
1. '.' - the empty area which every animal can stay or go through
2. '#' - the tree which is an obstacle
3. 'S' - the Squirrely
4. 'M' - a Mouse
5. 'P' - a Pig
6. 'N' - the nut which the Squirrely want to get
You should notice that there is one blank line before every test case. You may assume that there is one and only one nut in the forest and the number of animals in the forest will not exceed 5, and the input guarantees that there are at most 32 empty grids(including the original grids occupied by animals) in the map.
输出解释
For each test case, output a positive integer indicating the desired answer. You may assume that there is always exists a solution to get the nut, and the minimal number of steps should be made will not exceed 30.
输入样例
#......N ###.#### ###M#### ###.#### ###.#### ###S#### ######## ###.#### ##.....# #S.M.P.N ######## ######## ######## S...M.## ####M.## ####M.## ###P..## ####N.## P.....M# ...##..# P..##..# .###...# ..N#...# .###..S#
输出样例
4 4 5 15
提示
1. When a Mouse or Squirrely is adjacent to a Pig and a nut at the same time, it will be eaten by the Pig first. 2. At the beginning of the game, it’s guaranteed that you can’t win or fail at once. 3. When being able to eat or be eaten, the animal will stop and finish the eating process.Sample Explanations Case #1: 1. roll the Mouse at grid (3, 4) up to grid (1, 4). 2. roll the Mouse at grid (1, 4) left to grid (1, 2). 3. roll Squirrely at grid (6, 4) up to grid (1, 4). 4. roll Squirrely at grid (1, 4) right to grid(1, 7) and he can get the nut. Case #2: 1. roll the Pig at grid (4, 6) up to grid (3, 6). 2. roll the Pig at grid (3, 6) left to grid (3, 4), why grid (3, 4)? Because it will stop to eat the Mouse at grid (4, 4). 3. roll the Pig at grid (3, 4) up to grid (2, 4), you must roll the Pig to grid (2, 4), otherwise, Squirrely will certainly be eaten by the Pig! 4. just roll Squirrely at grid (4, 2) right to grid (4, 7) and he can get the nut. Case #3: 1. roll the Mouse at grid (4, 5) down to grid (5, 5), and it is eaten by the Pig, notice that the Mouse at grid(5, 5) can not eat the nut because the Mouse will be eaten by the Pig before it can eat the nut! 2. roll the Mouse at grid (3, 5) down. 3. roll the Mouse at grid (2, 5) down. 4. roll Squirrely at grid (2, 1) right to grid (2, 6). 5. roll Squirrely at grid (2, 6) down to grid (6, 6) and he can get the nut.
来自杭电HDUOJ的附加信息
| Recommend | hujie |
最后修改于 2020-10-25T23:18:55+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 2000/1000MS(Java/Others) | 65536/65536K(Java/Others) |
登陆或注册以提交代码