HDU 5433 Xiao Ming climbing

題目鏈接：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為當前剩余意念值。求在限定步數(shù)內(nèi)，從起點到終點到的最小體力消耗。

解題：

? ? 之前的代碼是錯誤的，多謝一抹憂傷|指出。深搜理論上不是不可以，但是還需要加一維代表步數(shù)，復(fù)雜度可能會挺高。故正解是，步數(shù)少，且代價低的優(yōu)先隊列配合BFS。

坑點：

? ? 當k=0的時候，不管起點和終點是否重合，要直接輸出No Answer，好像題面有提及，意念值為0，就意味著失敗。

錯誤代碼：

錯誤原因：

? ? 并不是新到達一點時，代價低，就更新該點，可能存在代價低，步數(shù)多不能到達的情況，而代價高，步數(shù)少，卻能到達。

#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]