注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1193(hnoi2006) 马步距离  

2013-03-06 13:54:25|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
乱搞题
参见立杰的代码……
让曼哈顿距离小于等于一个数再BFS
缩小曼哈顿距离之前的模拟就是贪心
贪心方法似乎是以距离为第一关键字横纵坐标差为第二关键字
膜拜立杰的空间吧……


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 200
using namespace std;
struct Point
{
    int x,y;
    void Read(){  scanf("%d %d",&x,&y);  }
    Point() {}
    Point(int x,int y): x(x),y(y) {}
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend Point operator + (const Point &a,const Point &b){  return Point(a.x+b.x,a.y+b.y);  }
    friend bool operator == (const Point &a,const Point &b){  return a.x==b.x&&a.y==b.y;  }
}S,T;
typedef Point Vector;
int dis(const Point &a,const Point &b){  return abs(a.x-b.x)+abs(a.y-b.y);  }
Vector p[10];
struct node
{
    Point p;
    int step;
    node() {}
    node(const Point &a,int p): p(a),step(p) {}
};
int BFS(Point S,Point T)
{
    S=S+Vector(50,50),T=T+Vector(50,50);
    static node queue[MAXN*MAXN],head,tail;
    static bool use[MAXN][MAXN];
    int front=0,rear=1;
    memset(use,false,sizeof(use));
    queue[rear]=node(S,0),use[S.x][S.y]=true;
    while(front<rear)
    {
        head=queue[++front];
        for(int i=0;i<8;i++)
        {
            tail=node(head.p+p[i],head.step+1);
            if(!use[tail.p.x][tail.p.y])
            {
                queue[++rear]=tail,use[tail.p.x][tail.p.y]=true;
                if(tail.p==T)  return tail.step;
            }
        }
    }
}
int work()
{
    p[0]=Vector(1,2),p[1]=Vector(1,-2),p[2]=Vector(-1,2),p[3]=Vector(-1,-2);
    p[4]=Vector(2,1),p[5]=Vector(2,-1),p[6]=Vector(-2,1),p[7]=Vector(-2,-1);
    int ans=0;
    while(dis(S,T)>10)
    {
        pair<int,int>Min;
        Point next;
        Min=make_pair(1<<30,1<<30);
        for(int i=0;i<8;i++)
        {
            Point newpoint=S+p[i];
            pair<int,int>Greedy=make_pair(dis(T,newpoint),abs(abs(newpoint.x-T.x)-abs(newpoint.y-T.y)));
            if(Min>Greedy)  next=newpoint,Min=Greedy;
        }
        S=next,ans++;
    }
    return ans+BFS(Point(0,0),T-S);
}
int main()
{
    S.Read(),T.Read();
    printf("%d\n",work());
    return 0;
}



  评论这张
 
阅读(475)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017