题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5433
Xiao Ming climbing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1346 Accepted Submission(s): 384
This mountain is pretty strange that its underside is a rectangle which size is n∗m and every little part has a special coordinate(x,y)and a height H.
In order to escape from this mountain,Ming needs to find out the devil and beat it to clean up the curse.
At the biginning Xiao Ming has a fighting will k,if it turned to 0 Xiao Ming won't be able to fight with the devil,that means failure.
Ming can go to next position(N,E,S,W)from his current position that time every step,(abs(H1−H2))/k 's physical power is spent,and then it cost 1 point of will.
Because of the devil's strong,Ming has to find a way cost least physical power to defeat the devil.
Can you help Xiao Ming to calculate the least physical power he need to consume.
Then T testcases follow.
The first line contains three integers n,m,k ,meaning as in the title(1≤n,m≤50,0≤k≤50).
Then the N × M matrix follows.
In matrix , the integer H meaning the height of (i,j),and '#' meaning barrier (Xiao Ming can't come to this) .
Then follow two lines,meaning Xiao Ming's coordinate(x1,y1) and the devil's coordinate(x2,y2),coordinates is not a barrier.
(The result should be rounded to 2 decimal places)
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
0.00
No Answer
题解：
看网上都是bfs的解法，这里来一发动态规划。
设dp[i][j][k]代表小明走到(i,j)时还剩k个单位的fighting will的状态；
令(i',j') 表示（i，j）上下左右的某一点，那么易得转移方程：
dp[i][j][k]=min(dp[i][j][k],dp[i'][j'][k+1]+abs(H[i][j]-H[i'][j'])/(k+1))
由于状态转移的顺序比较复杂，所有可以用记忆化搜索的方式来求解。
最终ans=min(dp[x2][y2][1],......,dp[x2][y2][k]]).
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=; double dp[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];
char mat[maxn][maxn]; int n,m,len;
int X1,Y1,X2,Y2; void init(){
memset(vis,,sizeof(vis));
memset(dp,0x7f,sizeof(dp));
} const int dx[]={-,,,};
const int dy[]={,,-,};
double solve(int x,int y,int k){
if(vis[x][y][k]) return dp[x][y][k];
vis[x][y][k]=;
for(int i=;i<;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<||tx>n||ty<||ty>m||k+>len||mat[tx][ty]=='#') continue;
double add=fabs((mat[x][y]-mat[tx][ty])*1.0)/(k+);
dp[x][y][k]=min(dp[x][y][k],solve(tx,ty,k+)+add);
}
return dp[x][y][k];
} int main(){
int tc;
scanf("%d",&tc);
while(tc--){
init();
scanf("%d%d%d",&n,&m,&len);
for(int i=;i<=n;i++) scanf("%s",mat[i]+);
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
dp[X1][Y1][len]=; vis[X1][Y1][len]=;
double ans=0x3f;
int flag=;
for(int k=len;k>=;k--){
double tmp=solve(X2,Y2,k);
if(ans>tmp){
flag=;
ans=tmp;
}
}
if(flag) printf("%.2lf\n",ans);
else printf("No Answer\n");
}
return ;
}