HDU 5433 Xiao Ming climbing
[導(dǎo)讀]題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5433
題面：
Xiao Ming climbing
Time Limit: 2000/1000
題目鏈接：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): 404????Accepted Submission(s): 93
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. ?
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. ?
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) ?
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 ?
Sample Output 1.03 0.00 No Answer
題目大意：
? ? 給定起點和終點。有一個意念值k，其實就是可以走k步。每走一步都會產(chǎn)生體力消耗abs(a1-a2)/x，a1，a2分別為兩個位置的高度，x為當(dāng)前剩余意念值。求在限定步數(shù)內(nèi)，從起點到終點到的最小體力消耗。
解題：
? ? 之前的代碼是錯誤的，多謝一抹憂傷|指出。深搜理論上不是不可以，但是還需要加一維代表步數(shù)，復(fù)雜度可能會挺高。故正解是，步數(shù)少，且代價低的優(yōu)先隊列配合BFS。
坑點：
? ? 當(dāng)k=0的時候，不管起點和終點是否重合，要直接輸出No Answer，好像題面有提及，意念值為0，就意味著失敗。
錯誤代碼：
錯誤原因：
? ? 并不是新到達(dá)一點時，代價低，就更新該點，可能存在代價低，步數(shù)多不能到達(dá)的情況，而代價高，步數(shù)少，卻能到達(dá)。
#include
using namespace std;
char map[55][55];
double dp[55][55];
int n,m,k,t,sx,sy,dx,dy,dir[4][2]={-1,0,0,1,1,0,0,-1};
bool flag;
void dfs(int x,int y,int step,double cost)
{
int tx,ty;
double tcost;
if(cost>=dp[x][y])return;
else
{
dp[x][y]=cost;
if(x==dx&&y==dy)
{
flag=true;
return;
}
if(step==0)return;
for(int i=0;i<4;i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]!='#')
{
tcost=cost+1.0*abs(map[x][y]-map[tx][ty])/step;
dfs(tx,ty,step-1,tcost);
}
}
}
}
void init()
{
flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=1e9;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
if(k==0)
{
printf("No Answern");
continue;
}
init();
dfs(sx,sy,k,0.0);
if(flag)
{
printf("%.2lfn",dp[dx][dy]);
}
else
printf("No Answern");
}
return 0;
} 修改代碼：
#include
#include
using namespace std;
char map[55][55];
double dp[55][55][55];
int n,m,k,t,sx,sy,dx,dy,dir[4][2]={-1,0,0,1,1,0,0,-1};
bool flag;
struct node
{
int x,y,step;
double cost;
bool operator<(const node &a)const
{
if(step!=a.step)
return step>a.step;
else
return cost>a.cost;
}
};
priority_queue qe;
void bfs()
{
while(!qe.empty())
qe.pop();
int tx,ty,tstep;
node tmp,cur;
tmp.x=sx,tmp.y=sy,tmp.cost=0.0,tmp.step=0;
qe.push(tmp);
while(!qe.empty())
{
cur=qe.top();
qe.pop();
if(cur.cost>=dp[cur.x][cur.y][cur.step])
continue;
else
{
dp[cur.x][cur.y][cur.step]=cur.cost;
if(cur.x==dx&&cur.y==dy)
{
flag=true;
continue;
}
if(cur.step==k)
continue;
for(int i=0;i<4;i++)
{
tx=cur.x+dir[i][0];
ty=cur.y+dir[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]!='#')
{
tmp.x=tx,tmp.y=ty,tmp.step=cur.step+1;
tmp.cost=cur.cost+(1.0*abs(map[cur.x][cur.y]-map[tx][ty])/(k-cur.step));
qe.push(tmp);
}
}
}
}
}
void init()
{
flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int x=0;x<=k;x++)
dp[i][j][x]=1e9;
}
int main()
{
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
if(k==0)
{
printf("No Answern");
continue;
}
init();
bfs();
if(flag)
{
ans=dp[dx][dy][0];
for(int i=1;i<=k;i++)
{
if(dp[dx][dy][i] 
下載文檔
