#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<math.h>#include<algorithm>#include<queue>#include<set>#include<bitset>#include<map>#include<vector>#include<stdlib.h>using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a) memset(a,0,sizeof(a))int n,m,k;int a,b,c,d;double minx;char ch[55];int mat[55][55];double vis[55][55][55];//vis[i][j][k]表示在（i，j）这个坐标的时候所剩k斗志的体力值int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};struct node{int x,y,t;//t为斗志double ans;//体力}s[100005];void bfs(node st){queue<node> q;node now, next;st.t=k;st.ans=0.0;vis[st.x][st.y][st.t]=0;q.push(st);while (!q.empty()){now = q.front();if (now.t<=0) return ;for (int i=0; i<4; i++)//平常的bfs{next.x = now.x+dir[i][0];next.y = now.y+dir[i][1];if (next.x<0||next.x>=n||next.y<0||next.y>=m) continue;if (mat[next.x][next.y]==-1) continue;next.ans = now.ans+(double)abs(mat[now.x][now.y]-mat[next.x][next.y])/(double)now.t;next.t = now.t-1;if (vis[next.x][next.y][next.t]-next.ans>0)//当前的得到的体力值比之前得到的体力值小{vis[next.x][next.y][next.t]=next.ans;//更新q.push(next);//入队}}q.pop();}return ;}int main (){int T;scanf ("%d",&T);while (T–){scanf ("%d%d%d",&n,&m,&k);for (int i=0; i<n; i++){scanf ("%s",ch);for (int j=0; j<m; j++){if (ch[j] == '#')mat[i][j] = -1;elsemat[i][j] = ch[j]-'0';}}scanf ("%d%d",&a,&b);scanf ("%d%d",&c,&d);if(k<=0){printf("No Answer\n");continue;}a–,b–,c–,d–;node st;st.x=a;st.y=b;//CL(vis);for (int i=0; i<=n; i++)//初始化for (int j=0; j<=m; j++)for (int r=0; r<=k; r++)vis[i][j][r]=INF;bfs(st);minx=vis[c][d][1];for (int i=1; i<=k; i++)//最后扫一遍，，得到最小体力minx=min(minx, vis[c][d][i]);if (minx-INF<0)printf ("%.2lf\n",minx);elseprintf ("No Answer\n");}return 0;}
最大的成功在于最大的付出。
