问题描述
小明因为受到大魔王的诅咒,被困到了一座荒无人烟的山上并无法脱离.这座山很奇怪:
这座山的底面是矩形的,而且矩形的每一小块都有一个特定的坐标$(x,y)$和一个高度$H$.
为了逃离这座山,小明必须找到大魔王,并消灭它以消除诅咒.
小明一开始有一个斗志值$k$,如果斗志为0则无法与大魔王战斗,也就意味着失败.
小明每一步都能从他现在的位置走到他的$(N,E,S,W)$四个位置中的一个,会消耗$(abs(H_1-H_2))/k$的体力,然后消耗一点斗志。
大魔王很强大,为了留下尽可能多的体力对付大魔王,小明需要找到一条消耗体力最少的路径.
你能帮助小明算出最少需要消耗的体力吗.
输入描述
第一行输入一个整数$T( 1 \leq T \leq 10 )$
接下来有$T$行$T$组数据，每组数据有三个整数$n,m,k$含义如题$(1 \leq n,m \leq 50, 0 \leq k \leq 50)$
接下来有$n$行,每行$m$个字符,如果是数字则表示$(i,j)$的高度$H(0 \leq H \leq 9)$,'#'表示障碍
最后两行分别输入小明的坐标$(x_1,y_1)$和大魔王的坐标$(x_2,y_2)$,小明和魔王都不在障碍上。
输出描述
每组数据对应输出满足要求的体力(保留两位小数)。
如果无法逃离,则输出"$No \ Answer$"
输入样例
3
4 4 5
2134
2#23
2#22
2221
1 1
3 3
4 4 7
2134
2#23
2#22
2221
1 1
3 3
4 4 50
2#34
2#23
2#22
2#21
1 1
3 3
输出样例
1.03
0.00
No Answer
