原创 ZOJ 译题: ZOJ 1649 – Rescue
ZOJ 1649 – Rescue
Angel 被 Moligpy 抓进了一个 N * M (N, M <= 200) 的监狱. 监狱由墙, 道路和看守组成.
Angel 的朋友们想要救她出来, 他们需要到达 Angel 所在的格子. 在移动时, 如果一个格子里有看守的话, 我们需要将其杀死才能进入那个格子里. 如果目标格子是墙的话, Angel 的朋友们将无法到达那个墙. 向上下左右四个方向移动 (不能移动到监狱外面) 都是需要 1 个单位时间, 杀死一个看守也是需要 1 个单位时间.
你的任务是计算到达 Angel 所在格子的最少时间.
输入
第一行两个整数, N 和 M.
接下来有 N 行, 每行有 M 个字符: “#” 表示墙, “x” 表示看守, “.” 表示道路, “a” 表示 Angel, “r” 表示 Angel 的一位朋友.
输出
输出到达 Angel 所在格子的最少时间. 如果无法到达, 输出 “Poor ANGEL has to stay in the prison all his life.” (不包括引号).
样例输入
7 8
#.#####.
#.a#..r.
#..#x…
..#..#.#
#…##..
.#……
……..
样例输出
13
出题者 CHEN, Xue
题目来源 ZOJ Monthly, October 2003
提交地址 http://acm.zju.edu.cn/show_problem.php?pid=1649
译者 ConcreteVitamin (http://blog.concretevitamin.com.cn/)
时间 4-6-2008
