[USACO2010 Feb Gold 【ice】]hash+BFS+n多个二分

【题目链接】http://ace.delos.com/ioigate
八中也有
【题目大意】
给定一个无穷大的棋盘，和上面的n个石头，n<=20000。他们的坐标范围是-1e9<=x<=1e9
然后有一只牛在上面滑。
它每次可能选上下左右这4个方向滑，如果遇到石头，那么它就会停下来，并且它没办法在不遇到石头的情况下停下来。
当然了，它是不能穿越石头的。
给定起点和终点，为最少滑多少步能到达终点。
保证有解。
【算法分析】
呃，就是一最短路问题，而边权都为1，所以就只裸的BFS。
由于只能碰到石头才停下，所有最多有4*n个可达位置。
然后扩展就比较纠结。。。可能离散化比较好写，但是离散化的话还要对相隔的搞多一层。
也不是非常好处理。
我就是写了12个二分，泪流满面地1Y。
我的扩展是这样的：
开两个数组装那些石头，
第一个是x为第一关键字，y为第二关键字排序的。
第二个是y为第一关键字，x为第二关键字排序的。
然后走的时候就像前向星那样二分出x(y)相等的区间，然后再找一个y(x)刚好小于(大于)当前点的石头，扩展即可。最后利用hash判下重。。。
【其它】。。。之前代码贴错了。
【CODE】
/*
ID:jie22221
TASK:ice
LANG:C++
*/
#include #include #include #define AA (*((Node*)A))
#define BB (*((Node*)B))
using namespace std;
const int N=25555;
const int INF=0x7FFFFFFF;
const int Mod=200003;
struct Node{int x,y;}S,T,p[N],q[N],L[N*4];
struct edge{Node data;edge *next;}*ls[Mod];
int n,step[N*4],ans=INF,head,tail,fa[N*4];

void init(){
memset(ls,0,sizeof(ls));
cin >> n >> S.x >> S.y >> T.x >> T.y;
for (int i=1;i<=n;i++){
cin >> p[i].x >> p[i].y;
q[i]=p[i];
}
}

int cmp_p(const void *A,const void *B){
if (AA.x!=BB.x) return AA.x-BB.x;
return AA.y-BB.y;
}

int cmp_q(const void *A,const void *B){
if (AA.y!=BB.y) return AA.y-BB.y;
return AA.x-BB.x;
}

Node Findu(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[St].x>=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (q[mid].x else r=mid-1;
if (q[r].x res.x=q[l].x+1;
res.y=W.y;
return res;
}

Node Findd(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[Ed].x<=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (q[mid].x>W.x) r=mid;
else l=mid+1;
res.x=q[l].x-1;
res.y=W.y;
return res;
}

Node Findl(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || p[St].y>=W.y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (p[mid].y else r=mid-1;
if (p[r].y res.x=W.x;
res.y=p[l].y+1;
return res;
}

Node Findr(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || W.y>=p[Ed].y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (W.y else l=mid+1;
res.x=W.x;
res.y=p[l].y-1;
return res;
}

inline long long ABS(int x){
if (x<0) return -x;
return x;
}
inline int f(Node W){return (int)(((ABS(W.x)*17+ABS(W.y)*31)&INF)%Mod);}

bool Inhash(Node W){
for (edge *t=ls[f(W)];t;t=t->next)
if (t->data.x==W.x && t->data.y==W.y) return true;
return false;
}

void Insert(Node W){
edge *t=(edge *)malloc(sizeof(edge));
int h=f(W);
t->next=ls[h];
t->data=W;
ls[h]=t;
}

void expand(Node res){
if (res.x==INF || Inhash(res)) return;
Insert(res);
tail++;
L[tail]=res;
step[tail]=step[head]+1;
fa[tail]=head;
if (res.x==T.x && res.y==T.y)
ans=min(ans,step[tail]);
}

int solve(){
if (S.x==T.x && S.y==T.y) return 0;
L[0].x=S.x; L[0].y=S.y; step[0]=0; Insert(L[0]);
for (head=0,tail=0;head<=tail;head++){
expand(Findu(L[head]));
expand(Findd(L[head]));
expand(Findl(L[head]));
expand(Findr(L[head]));
if (ans }
return ans;
}

int main(){
freopen("ice.in","r",stdin);
freopen("ice.out","w",stdout);
ios::sync_with_stdio(false);
init();
qsort(p+1,n,sizeof(Node),cmp_p);
qsort(q+1,n,sizeof(Node),cmp_q);
cout << solve() << endl;
}