因为初始坐标忘了离散查了好久...
总耗时1037ms 峰值内存29.203 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define A first
#define B second
#define mp make_pair
#define M 100005
using namespace std;

void read(int &x){
x=0; char c=getchar();
for (; c<'0'; c=getchar());
for (; c>='0'; c=getchar())x=(x<<3)+(x<<1)+(c^'0');

}
int n,m,xx[M],yy[M],qx[M],qy[M],mxx,mxy;
struct AAA{
int cx[4],cy[4];
void ycl(){
cx[0]=0; cx[1]=-1; cx[2]=0; cx[3]=1;
cy[0]=-1; cy[1]=0; cy[2]=1; cy[3]=0;
}

struct AC{int x,y,t;};
int dis[1005][1005][5];
bool can[1005][1005];

AC cl(int x,int y,int d,int t){
// printf("--%d--\n",d);
// printf("x:%d y:%d\n",cx[d],cy[d]);
for (; x&&y&&x<mxx&&y<mxy&&can[x][y]&&dis[x][y][d]==-1; x+=cx[d],y+=cy[d])dis[x][y][d]=t;//,printf("%d %d\n",x,y);
if (!can[x][y])return (AC){x-cx[d],y-cy[d],t};
else return (AC){0,0,-1};
}
queue<AC>q;

void solve(int x,int y){
int i,j,t;
ycl();
memset(can,1,sizeof(can));
memset(dis,-1,sizeof(dis));
for (i=1; i<=n; i++){can[xx[i]][yy[i]]=0;}
for (i=0; i<4; i++)if (dis[x][y][i]==-1&&can[x+cx[i]][y+cy[i]])q.push(cl(x,y,i,1));
for (; !q.empty(); ){
t=q.front().t; x=q.front().x; y=q.front().y; q.pop();
if (t==-1)continue;
t++;
for (i=0; i<4; i++)if (dis[x][y][i]==-1&&can[x+cx[i]][y+cy[i]])q.push(cl(x,y,i,t));
}

for (i=1; i<=m; i++){
int res=-1;
x=qx[i]; y=qy[i];
for (j=0; j<4; j++){
if (dis[x][y][j]!=-1){
if (res!=-1)res=min(res,dis[x][y][j]); else res=dis[x][y][j];
}
}
printf("%d ",res);

}
}

}p70;

struct CCC{
int sx[M<<1],sy[M<<1];
int ans[M],cntx,cnty;
vector< pii >dax[M<<1],day[M<<1];

int chx(int l,int r,int x){
int mid;
for (; l<=r; ){
mid=(l+r)>>1;
if (sx[mid]==x)return mid;
if (sx[mid]>x)r=mid-1;
else l=mid+1;

}
return 0;
}
int chy(int l,int r,int x){
int mid;
for (; l<=r; ){
mid=(l+r)>>1;
if (sy[mid]==x)return mid;
if (sy[mid]>x)r=mid-1;
else l=mid+1;

}
return 0;
}
void clx(int x){
int i,cnt=0;
sx[++cnt]=x;
for (i=1; i<=n; i++)sx[++cnt]=xx[i];
for (i=1; i<=m; i++)sx[++cnt]=qx[i];
sort(sx+1,sx+cnt+1);
cnt=unique(sx+1,sx+cnt+1)-sx-1;
for (i=1; i<=n; i++)xx[i]=chx(1,cnt,xx[i]);
for (i=1; i<=m; i++)qx[i]=chx(1,cnt,qx[i]);
cntx=cnt;

}

void cly(int y){
int i,cnt=0;
sy[++cnt]=y;
for (i=1; i<=n; i++)sy[++cnt]=yy[i];
for (i=1; i<=m; i++)sy[++cnt]=qy[i];
sort(sy+1,sy+cnt+1);
cnt=unique(sy+1,sy+cnt+1)-sy-1;
for (i=1; i<=n; i++)yy[i]=chy(1,cnt,yy[i]);
for (i=1; i<=m; i++)qy[i]=chy(1,cnt,qy[i]);
cnty=cnt;

}

struct AC{int x,y,t;};
queue<AC>q;
map< pii,bool >vis;

AC cl0(int x,int y,int t){
int i;
for (i=0; i<dax[x].size()&&dax[x][i].A<y; i++);
if (i==dax[x].size())return (AC){0,0,-1};

for (; i<dax[x].size(); i++){
if (dax[x][i].B){
if (!ans[dax[x][i].B])ans[dax[x][i].B]=t;
else ans[dax[x][i].B]=min(ans[dax[x][i].B],t);
}
else{
y=chy(1,cnty,sy[dax[x][i].A]-1);
if (!y)return (AC){0,0,-1};
return (AC){x,y,t};
}

}
return (AC){0,0,-1};
}

AC cl1(int x,int y,int t){
int i;
for (i=dax[x].size()-1; i>=0&&dax[x][i].A>y; i--);
if (i==-1)return (AC){0,0,-1};

for (; i>=0; i--){
if (dax[x][i].B){
if (!ans[dax[x][i].B])ans[dax[x][i].B]=t;
else ans[dax[x][i].B]=min(ans[dax[x][i].B],t);
}
else{
y=chy(1,cnty,sy[dax[x][i].A]+1);
if (!y)return (AC){0,0,-1};
return (AC){x,y,t};
}

}
return (AC){0,0,-1};
}

AC cl2(int x,int y,int t){
int i;
for (i=0; i<day[y].size()&&day[y][i].A<x; i++);
if (i==day[y].size())return (AC){0,0,-1};

for (; i<day[y].size(); i++){
if (day[y][i].B){
if (!ans[day[y][i].B])ans[day[y][i].B]=t;
else ans[day[y][i].B]=min(ans[day[y][i].B],t);
}
else{
x=chx(1,cntx,sx[day[y][i].A]-1);
if (!x)return (AC){0,0,-1};
return (AC){x,y,t};
}

}
return (AC){0,0,-1};
}

AC cl3(int x,int y,int t){
int i;
for (i=day[y].size()-1; i>=0&&day[y][i].A>x; i--);
if (i==-1)return (AC){0,0,-1};

for (; i>=0; i--){
if (day[y][i].B){
if (!ans[day[y][i].B])ans[day[y][i].B]=t;
else ans[day[y][i].B]=min(ans[day[y][i].B],t);
}
else{
x=chx(1,cntx,sx[day[y][i].A]+1);
if (!x)return (AC){0,0,-1};
return (AC){x,y,t};
}

}
return (AC){0,0,-1};
}

void solve(int x,int y){
int xxx=x,yyy=y;
clx(xxx); cly(yyy);
// memset(ans,-1,sizeof(ans));
xxx=x=chx(1,cntx,x); yyy=y=chy(1,cnty,y);
int i;
for (i=1; i<=n; i++)dax[xx[i]].pb(mp(yy[i],0)),day[yy[i]].pb(mp(xx[i],0));
for (i=1; i<=m; i++)dax[qx[i]].pb(mp(qy[i],i)),day[qy[i]].pb(mp(qx[i],i));
for (i=1; i<=cntx; i++)sort(dax[i].begin(),dax[i].end());
for (i=1; i<=cnty; i++)sort(day[i].begin(),day[i].end());

q.push((AC){x,y,0});
int t;
for (; !q.empty();){
t=q.front().t; x=q.front().x; y=q.front().y; q.pop();
if (vis[mp(x,y)])continue;
vis[mp(x,y)]=1;
t++;
AC nx;
nx=cl0(x,y,t); if (nx.t!=-1)q.push(nx);
nx=cl1(x,y,t); if (nx.t!=-1)q.push(nx);
nx=cl2(x,y,t); if (nx.t!=-1)q.push(nx);
nx=cl3(x,y,t); if (nx.t!=-1)q.push(nx);
}
for (i=1; i<=m; i++){
if (qx[i]==xxx&&qy[i]==yyy){printf("0 "); continue;}
if(ans[i])printf("%d ",ans[i]);
else printf("-1 ");
}
}
}p100;

int main(){
// freopen("escape.in","r",stdin);
// freopen("escape.out","w",stdout);
int xxx,yyy;
read(n); read(m); read(xxx); read(yyy);
int i;
for (i=1; i<=n; i++){read(xx[i]); read(yy[i]); mxx=max(xx[i],mxx); mxy=max(yy[i],mxy);}
for (i=1; i<=m; i++){read(qx[i]); read(qy[i]); mxx=max(qx[i],mxx); mxy=max(qy[i],mxy);}
mxx++; mxy++;
p100.solve(xxx,yyy);

return 0;
}

表示没有楼下的方法效率高……

本菜按照横坐标和纵坐标从小到大（横坐标优先）对所有点（包括出口和障碍）排序，存入数组A，再按照纵坐标优先对所有点排序存入数组B。

然后……就是无比暴力的BFS，找队列中每个点的上下左右分别能到达的最近的点（根据方向二分数组A或B），如果是出口就穿过继续找……判断是否到过这个点（判重）用了哈希……

打了2个快排和4个方向的二分……代码果断5.9KB……200多行……不过效率跟楼下的大牛差不多，欣喜激动中……

测试数据 #0: Accepted, time = 0 ms, mem = 64412 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 64408 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 64408 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 64408 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 64408 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 64408 KiB, score = 10
测试数据 #6: Accepted, time = 436 ms, mem = 64408 KiB, score = 10
测试数据 #7: Accepted, time = 670 ms, mem = 64408 KiB, score = 10
测试数据 #8: Accepted, time = 421 ms, mem = 64412 KiB, score = 10
测试数据 #9: Accepted, time = 296 ms, mem = 64412 KiB, score = 10
Accepted, time = 1947 ms, mem = 64412 KiB, score = 100

真的是写了整整一天啊QAQ
一开始用map映射结果TLE……
中途连朴素都差错半天……
哈希+二分查找……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 100010
#define inf 0x7fffffff/2
const int p=5133613;
using namespace std;
int n,m,sx,sy,d[p],head[p],cnt;
bool vis[p];
struct p1{
int x,y;
bool operator<(const p1 &a)const{
if(x!=a.x)return x<a.x;
return y<a.y;
}
}o1[maxn],e1[maxn];
struct p2{
int x,y;
bool operator<(const p2 &a)const{
if(y!=a.y)return y<a.y;
return x<a.x;
}
}o2[maxn],e2[maxn];
struct point{
int x,y,next;
bool operator <(const point &a)const{
if(x!=a.x)return x<a.x;
return y<a.y;
}
}ex[maxn],h[p];
queue<point>Q;
inline int hash(int x,int y){
int a=(x*11+y*7)%p;
for(int i=head[a];i;i=h[i].next){
if(h[i].x==x&&h[i].y==y)return i;
}
h[++cnt]=(point){x,y,head[a]};
head[a]=cnt;
return cnt;
}
inline void push(int x,int y,int a,int b){
if(vis[hash(x,y)])return;
vis[hash(x,y)]=1;
d[hash(x,y)]=d[hash(a,b)]+1;
Q.push((point){x,y,555});
}
void bfs(){
while(!Q.empty()){
point c=Q.front();Q.pop();
int x=c.x,y=c.y,u=hash(x,y);

p1 u1={x,y};
p2 u2={x,y};
int a=lower_bound(o1+1,o1+n+1,u1)-o1;
int b=lower_bound(o2+1,o2+n+1,u2)-o2;
int left=-inf,right=inf,up=inf,down=-inf;

if(o1[a].x==x){
up=o1[a].y;

push(x,up-1,x,y);
}

if(o1[a-1].x==x){
down=o1[a-1].y;
push(x,down+1,x,y);
}
if(o2[b].y==y){
right=o2[b].x;
push(right-1,y,x,y);
}
if(o2[b-1].y==y){
left=o2[b-1].x;
push(left+1,y,x,y);
}

a=lower_bound(e1+1,e1+m+1,u1)-e1;
b=lower_bound(e2+1,e2+m+1,u2)-e2;
for(int i=a;e1[i].x==x&&e1[i].y<up;i++){
int v=hash(e1[i].x,e1[i].y);
if(!vis[v]){
vis[v]=1;
d[v]=d[u]+1;
}
}
for(int i=a-1;e1[i].x==x&&e1[i].y>down;i--){
int v=hash(e1[i].x,e1[i].y);
if(!vis[v]){
vis[v]=1;
d[v]=d[u]+1;

}
}

for(int i=b;e2[i].y==y&&e2[i].x<right;i++){
int v=hash(e2[i].x,e2[i].y);
if(!vis[v]){
vis[v]=1;
d[v]=d[u]+1;
}
}
for(int i=b-1;e2[i].y==y&&e2[i].x>left;i--){

int v=hash(e2[i].x,e2[i].y);

if(!vis[v]){
vis[v]=1;
d[v]=d[u]+1;

}
}

}
}
int main(){
scanf("%d%d%d%d",&n,&m,&sx,&sy);
memset(d,-1,sizeof(d));
d[hash(sx,sy)]=0;
vis[hash(sx,sy)]=1;
Q.push((point){sx,sy,0});
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
o1[i].x=o2[i].x=a;
o1[i].y=o2[i].y=b;

}
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
ex[i].x=e1[i].x=e2[i].x=a;
ex[i].y=e1[i].y=e2[i].y=b;
}
sort(o1+1,o1+n+1);
sort(o2+1,o2+n+1);
sort(e1+1,e1+m+1);
sort(e2+1,e2+m+1);
bfs();
for(int i=1;i<=m;i++){
int v=hash(ex[i].x,ex[i].y);
printf("%d",d[v]);
if(i==m)putchar('\n');else putchar(' ');
}

return 0;
}

how to做

求教怎么构图

嘿嘿,教主的标程才170行,4KB......

首先，障碍很小，如果排序的话很容易扫一遍就知道所有点的后继是什么。但是，这一要注意，有8个方向，不是4个！！一个障碍从左边和从右边来的上下是不一样的！！所以说，我的暴力方法是用了8个快排，对应八种情况，各个扫描一遍（其实完全可以合并的，懒得改了）。注意，这里求的是原来点的后继，与当前的下标是不一样的！！这里一定要把结束点和障碍分开讨论！！！

只有就是结束点。并不是到结束点就结束了，可能穿过结束点继续道下一个障碍没问题！！于是每个结束点的后继在求一下，这里就只有4个了。

还有，过结束点的时候路径长不用加1，过障碍要加1。发现了什么问题么？这违背了BFS的原则！！先到的时候路径不一定最短！！我无奈之下，把BFS改动了一点变成了SPFA！

之后一个巨麻烦无比的长达700行的程序就诞生了。不过效率不错，总算是AC了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 384ms

├ 测试数据 08：答案正确... 572ms

├ 测试数据 09：答案正确... 384ms

├ 测试数据 10：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1828ms

怎么做呀　？

牛们

膜拜ltw牛...才自学C没多久就用C在1389ms把它搞出来了...教主都是4000+ms啊！

题解：BFS+BT

极点 7个了！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

被虐了..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

历史最低

难的让人心寒。

真他妈难？

这难道是难度0吗？

1个人通过

是orz教主自己？

题目改成1行内输出了

养成良好编程习惯

行末换行，不加空格

猥琐BFS

zai chu xian

地下室