HDU 3158 PropBot（DFS）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3158

2
24 5.0 5.0
9 7.0 17.0

0.502525
0.100505

题意：

每次有两个操作：

1、直线距离走10cm；

2、向右转45°；

每一个操作耗时为一秒。问在给定的时间内，能走到的离目标点最近的距离？

PS:

DFS每一步的每个方向，记录出现的最短距离；

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double dd = sqrt(2.0)/2*10;

int ti;
double x,y;
double d;

double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void dfs(double x1,double y1,int dir,int tt)
{
    double aa;
    dir %= 8;
    aa=dis(x1,y1,x,y);
    if(aa < d)
    {
        d = aa;
    }
    if(tt==ti ||(aa-10*(ti-tt)>d))//如果剩下的步数就算走直线都比当前的d大就不用往下搜了
    {
        return ;
    }
    if(dir == 0)//沿+x走10cm
    {
        dfs(x1+10,y1,dir,tt+1);
    }
    else if(dir == 1)//沿+x偏-y为45°方向走10cm
    {
        dfs(x1+dd,y1-dd,dir,tt+1);
    }
    else if(dir == 2)//沿-y走10cm
    {
        dfs(x1,y1-10,dir,tt+1);
    }
    else if(dir == 3)//沿-y偏-x为45°方向走10cm
    {
        dfs(x1-dd,y1-dd,dir,tt+1);
    }
    else if(dir == 4)//沿-x走10cm
    {
        dfs(x1-10,y1,dir,tt+1);
    }
    else if(dir == 5)//沿-x偏+y为45°方向走10cm
    {
        dfs(x1-dd,y1+dd,dir,tt+1);
    }
    else if(dir == 6)//沿+y走10cm
    {
        dfs(x1,y1+10,dir,tt+1);
    }
    else if(dir == 7)//沿+y偏+x为45°方向走10cm
    {
        dfs(x1+dd,y1+dd,dir,tt+1);
    }
    dfs(x1,y1,dir+1,tt+1);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lf%lf",&ti,&x,&y);
        d = dis(0,0,x,y);
        dfs(0,0,0,0);
        printf("%.6lf\n",d);
    }
    return 0;
}
/*
2
24 5.0 5.0
9 7.0 17.0

5
9 7.0 17.0
*/

HDU 3158 PropBot（DFS）

原文：http://blog.csdn.net/u012860063/article/details/39860551