问题 3918 --营救小明

3918: 营救小明

时间限制: 1 Sec  内存限制: 32 MB
提交: 123  解决: 26
[提交][状态][讨论版][命题人:]

题目描述

一天,小明梦见自己被外星人抓走了,他被关在了一座监狱里,这座监狱形如N*M(N,M<=200)的矩阵,监狱里有墙、道路和守卫。
小明的小伙伴们得知他被外星人抓走后想要把他救出来,他们要试图接近关押小明的那间房间。当他们经过有守卫的房间时他们必须干掉守卫后继续前进,而当遇到墙的时候则只能绕道。他们只能向上下左右四个方向移动,每移动一次耗时1分钟,干掉一个守卫也耗时1分钟。不必担心,他们足够强壮,可以干掉任何一个守卫。
现在请你计算出他们当中最快到达小明所在房间的那个人最短需要花费多长时间。

输入

输入包含多组测试数据。
每组输入的第一行是两个整数N和M(N,M<=200)。
接下来N行,每行输入M个字符。“.”代表道路,可以通行。“#”代表墙。“g”代表守卫。“m”代表小明所在的房间。“f”代表每一个小明的小伙伴,可能有多个小伙伴一起来救他。

输出

对于每组输入,输出小伙伴当中最快到达小明所在房间的那个人最短需要花费多长时间。如果所有小伙伴都无法到达小明所在的房间的话,请输出“Poor Xiaoming”(引号不输出)。

样例输入

7 8
#.#####. 
#.m#..f. 
#..#g... 
..#..#.# 
#...##.. 
.#...... 
........

样例输出

13

来源

 

[提交][状态]