题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5433
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
typedef pair<int,int> pii;
const int maxn =50+7;
const int mod=1e9+7;
const double INF =1e20+7;
const double EPS=1e-6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：在一张地图上给定初始位置
和终点位置，和一个初始化能量，
每走一格需要消耗一个能量，
走一格获得的权重是两格高度差除以当前能量值，
问走到终点在能量格允许的情况下所收获权重最小是多少。以前的标准最短路只需要二维就可以标记状态，
现在要多一个维度k,用优先队列最小堆去扩充状态，
所以走过的三维状态就没必要走第二次，（堆里最多有50^3个状态）
然后用当前的状态去进行差分约束，
更新周围的状态，如果更新成功，则那个状态又成为了新的扩展状态。
最后的答案是通过枚举k来得到的，注意k为0是个不可行状态。一些细节：k可以为0...所以在判定的时候注意下。*/
char ch[maxn];
int n,m,k,mp[maxn][maxn];
int sx,sy,ex,ey;struct node
{int x,y,s;///步数double v;///权重bool operator<(const node& y) const{return v>y.v;}
};int dx[]={0,0,1,-1},dy[]={1,-1,0,0};///方向数组
bool judge(int x,int y)
{if(x<=0||x>n) return false;if(y<=0||y>m) return false;return true;
}bool Eq(double x,double y){return abs(x-y)<=EPS;}
double cnt(int x1,int y1,int x2,int y2,int kk){return 1.0*abs(mp[x1][y1]-mp[x2][y2])/(1.0*kk);}double d[maxn][maxn][maxn];
int done[maxn][maxn][maxn];
void spfa(int sx,int sy)
{priority_queue<node> pq;pq.push(node{sx,sy,k,0});memset(done,0,sizeof(done));for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int q=0;q<=k;q++) d[i][j][q]=INF;d[sx][sy][k]=0;///初始化距离数组while(!pq.empty()){node tp=pq.top();pq.pop();int x=tp.x,y=tp.y,s=tp.s;if(done[x][y][s]) continue;done[x][y][s]=1;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];int ts=s-1;if(!judge(tx,ty)) continue;///越界if(mp[tx][ty]==-1) continue;if(ts<=0) continue;double tmp=cnt(tx,ty,x,y,s)+d[x][y][s];if(d[tx][ty][ts]>tmp){d[tx][ty][ts]=tmp;pq.push(node{tx,ty,ts,tmp});}}}double ans=INF;for(int i=1;i<=k;i++) ans=min(ans,d[ex][ey][i]);if(!Eq(ans,INF)) printf("%.2f\n",ans);else puts("No Answer");
}int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%s",ch+1);for(int j=1;j<=m;j++){if(ch[j]=='#') mp[i][j]=-1;else mp[i][j]=ch[j]-'0';}}scanf("%d%d",&sx,&sy);scanf("%d%d",&ex,&ey);spfa(sx,sy);}return 0;
}