Problem O: 29-搜索练习-救援 Problem O: 29-搜索练习-救援
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 2 Solved: 1
[Submit] [Status] [Web Board] [Creator:]Description
Angel被困在一个N*M的监狱，迷宫有墙，道路，还有守卫者，Angel的朋友想要去救他，他们的任务是，到达Angel所在的位置。他们可以上下左右四个方向移动，每次移动花费一体力，可以选择击杀守卫者，也花费1体力。
Input
第一行两个整数N和M，表示迷宫的大小
之后一个N*M的矩阵，‘.’表示道路，'a'代表Angel
‘r’代表Angel的任一个朋友。'x'表示守卫者。
Output
输出最小花费，如果不能到达，输出“Poor ANGEL has to stay in the prison all his life.”；
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output
13
[Submit][Status]