问题说明

小未得到了一张古老的藏宝图，但他一个人不敢前去探险，叫上他的小伙伴一起去。藏宝图显示宝藏在一个如N*M的区域内（N,M<=200），而且有多个入口，该区域内有很多障碍物(不可通行)、小路、陷阱(可以通过但要费更长的时间)情况非常复杂。由于到达该地已经很晚了，想尽快找到宝藏，所以他们计划分组行动，每个入口都派人进入。

      他们只能向上下左右四个方向移动，每移动一次耗时1分钟，越过陷阱要花5分钟。不必担心，他们足够聪明，可以越过任何陷阱只要有时间。现在请你计算出他们当中最快找到宝藏那组人最短需要花费多长时间。

输入格式

第一行是两个整数N和M（N,M<=200）。
接下来N行，每行输入M个字符，“.”代表道路可以通行，“#”代障碍物，“x”代表陷阱，“w”代表宝藏所在位置。“r”代表每一个入口。

输出格式

输出小伙伴当中最快找到宝藏需要花费多长时间。如果所有小伙伴们都无法到达宝藏点，请输出“no path”

样例输入：

4 4
rx#r
#w#.
#...
####

样例输出

5

7 8
#.#####. 
#.w#..r. 
#..#x... 
..#..#.# 
#...##.. 
.#...... 
........

14

来源/分类