Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 438 Accepted Submission(s): 108
Problem Description
Due to the curse made by the devil,Xiao Ming is stranded on a mountain and can hardly escape.
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.
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.
Input
The first line of the input is a single integer T(T≤10),
indicating the number of testcases.
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.
indicating the number of testcases.
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.
Output
For each testcase print a line ,if Xiao Ming can beat devil print the least physical power he need to consume,or output "NoAnswer"
otherwise.
(The result should be rounded to 2 decimal places)
otherwise.
(The result should be rounded to 2 decimal places)
Sample Input
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
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
Sample Output
1.03
0.00
0.00
No Answer
这题用宽搜做，用minx[x][y][d]表示走到(x,y)且剩余斗志为d的最少体力，bfs的过程中，只有满足边界条件并且下一步算出来的值要小于min[xx][yy][d]时才把这个点放入队列。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 999999999
#define maxn 10050
char gra[55][55];
int vis[55][55];
int tab[10][2]={0,1,-1,0,0,-1,1,0};
int n,m,k,x3,x2,y3,y2;
struct node{
double tili;
int x,y,douzhi;
}q[1111111];
double minx[55][55][55];
void bfs()
{
int i,j,front,rear,x,y,xx,yy,douzhi,dou;
double tili,ti;
front=rear=1;
q[front].x=x3;q[front].y=y3;q[front].tili=0;q[front].douzhi=k;
while(front<=rear){
x=q[front].x;y=q[front].y;tili=q[front].tili;douzhi=q[front].douzhi;
front++;
//printf("%d %d %.2f %d\n",x,y,tili,douzhi);
if(x==x2 && y==y2){
continue;
}
for(i=0;i<4;i++){
xx=x+tab[i][0];yy=y+tab[i][1];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && gra[xx][yy]!='#'){
ti=tili+fabs(gra[xx][yy]-gra[x][y])/(double)douzhi;
dou=douzhi-1;
if(dou==0 || ti>=minx[xx][yy][dou]){
continue;
}
minx[xx][yy][dou]=ti;
rear++;
q[rear].x=xx;q[rear].y=yy;q[rear].tili=ti;q[rear].douzhi=dou;
}
}
}
}
int main()
{
int i,j,T,h;
double ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++){
scanf("%s",gra[i]+1);
}
scanf("%d%d%d%d",&x3,&y3,&x2,&y2);
if(k==0){
printf("No Answer\n");continue;
}
if(x2==x3 && y2==y3){
printf("0.00\n");continue;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
for(h=1;h<=k;h++){
minx[i][j][h]=inf;
}
}
}
minx[x3][y3][k]=0;
bfs();
ans=inf;
for(i=1;i<=k;i++){
if(ans>minx[x2][y2][i]){
ans=minx[x2][y2][i];
}
}
if(ans==inf){
printf("No Answer\n");
}
else printf("%.2f\n",ans);
}
return 0;
}