09年一部风靡全球的动画片飞屋环球记

09年一部风靡全球的动画片飞屋环球记 09年一部风靡全球的动画片飞屋环球记，片中的主人公是一位年逾花甲的老人。为了追寻年轻时探险南美洲的梦想，他把成千上万个气球绑在屋顶，连人带屋飞起来。他驾驶这个“会飞”的屋子，向梦想进发～然而这个类似热气球的飞屋很难驾驶，受风的影响很大，如果他本意向前飞的话，会有0.25的可能性向左拐，也会有0.25的可能性向右拐，只有0.5的可能性向前飞。以图1为例，如果他想从D4像北飞，则飞到D3，C4,D5的概率分别为0.25，0.5，0.25;如果他从B4向东飞，则飞到A4,B5,C4的概率分别为0.25，0.5，0.25 更糟糕的是，飞屋上方的气球会受天气影响而破裂，比如在C5处正在发生暴风雪，如果飞行到这个空域则破裂的气球会比晴朗区域多很多，此外由于高山的阻隔，某些空域是无法抵达的，比如图1中的B2，B3这样的位置。老人希望能抵达目标，如A6。而且他希望在这个过程中可能破裂的气球最少。请你为老人找到这样一条最优的路径。 注:如果前方是高山或地图的边缘，飞屋会回到原来的格子(飞不动) 1 2 3 4 5 6 A 目的地 B 山 山 C 山 山 暴风雨 D 气球和屋 图一:飞屋环游示意图 输入:输入中包含多个样例，每个样例的首行是两个数字W和H，之间用一个空格分开。分别代地图的宽度和高度(两者都小于20)。后续的H行包含了地图的具体信息，其中每一行都由W个字符或数值组成，每个字符或数值之间有一个空格分开。字符“S”代表老人的起点，“e”代表老人的目标，数字0代表此处有山，非零的整数(1或者100)代表在此处飞行会破裂的气球数目。 输出:请计算老人从起点至目标的最佳行进路线，并输出每一步的行进方向，其中e,w,s,n四个字符分别代表东南西北四个方向。输出字符之间无空格，每个样例的输出占单独一行。 实例: 输入 输出 4 6 wwwnnneeeee 1 1 1 1 1 e 1 0 0 1 1 1 1 0 0 1 100 1 1 1 1 s 1 1 用求精算法写出步骤或直接写出程序代码 语言不限～