M萌--怪兽的伤害

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

这是个什么问题呢?DP,贪心,数据结构,图论,数论还是计算几何?管他呢,反正胖巨巨都会,虽然胖巨巨走得早。
 
现在有一张地图,为了方便,我们将它简化成n行m列。和往常做过的题一样,S表示起点,T表示终点,
*表示可以走,#表示不可以走。与往常不同的是,这张地图的每个点上住着一头怪兽,每经过一次就
会被该怪兽攻击并造成Xij点伤害。现在胖巨巨想知道从S到T受到的最小伤害是多少。

Input

 多组输入,对于每组输入:
第一行包含两个整数n,m(1 <= n,m <= 20,1 < n*m)。
接下来的n行,每行包含m个字符(仅包含 'S', 'T', '*', '#')。
接下来的n行,每行包含m个数字,表示每个点的伤害Xij(0 <= Xij <= 10000)。

Output

 若从S可以到达T,输出受到的最小伤害,否则输出"longlonggaijianfeile"。

Sample Input

2 2
S*
*T
1 2
10 100
2 2
S#
#T
1 1
1 1
3 3
*S*
*#*
#T*
1 2 3
4 5 6
7 8 9

Sample Output

103
longlonggaijianfeile
28

Hint

 

Source

zmx