讨论 / 上百度查的,看不懂
lijie201602 2017-09-23 23:39:09
点我顶贴 收藏 删除
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int oo=0x3f3f3f3f;

int fir[4000],ne[40000],to[40000],len[40000],que[4000000],

num[35][35][5],dis[4000],map[35][35],qbfsx[4000000],qbfsy[4000000],qbfst[4000000],

xx[]={1,-1,0,0},yy[]={0,0,1,-1},m,n,q,tot,cnt,ex,ey,sx,sy,tx,ty;

bool vis_bfs[35][35];

void add(int f,int t,int l)

{

cnt++;

ne[cnt]=fir[f];

fir[f]=cnt;

to[cnt]=t;

len[cnt]=l;

}

int bfs(int fx,int fy,int tx,int ty,int bx,int by)

{

if (fx==tx&&fy==ty) return 0;

int i,j,k,x,y,z,hd=1,tl=1,t;

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

vis_bfs[i][j]=0;

qbfsx[1]=fx;

qbfsy[1]=fy;

qbfst[1]=0;

vis_bfs[fx][fy]=1;

while (hd<=tl)

{

x=qbfsx[hd];

y=qbfsy[hd];

t=qbfst[hd];

hd++;

for (k=0;k<4;k++)

if (map[x+xx[k]][y+yy[k]]&&(x+xx[k]!=bx||y+yy[k]!=by)&&!vis_bfs[x+xx[k]][y+yy[k]])

{

if (x+xx[k]==tx&&y+yy[k]==ty) return t+1;

tl++;

qbfsx[tl]=x+xx[k];

qbfsy[tl]=y+yy[k];

qbfst[tl]=t+1;

vis_bfs[x+xx[k]][y+yy[k]]=1;

}

}

return oo;

}

int spfa()

{

int i,j,k,p,x,y,z,hd,tl,ans;

if (sx==tx&&sy==ty) return 0;

for (i=1;i<=tot;i++)

dis[i]=oo;

for (k=0;k<4;k++)

if (num[sx][sy][k])

{

dis[num[sx][sy][k]]=bfs(ex,ey,sx+xx[k],sy+yy[k],sx,sy);

que[k+1]=num[sx][sy][k];

}

hd=1;

tl=4;

while (hd<=tl)

{

p=que[hd++];

for (i=fir[p];i;i=ne[i])

if (dis[to[i]]>dis[p]+len[i])

{

dis[to[i]]=dis[p]+len[i];

que[++tl]=to[i];

}

}

ans=oo;

for (k=0;k<4;k++)

if (num[tx][ty][k])

ans=min(ans,dis[num[tx][ty][k]]);

return ans==oo?-1:ans;

}

int main()

{

int i,j,k,x,y,z;

scanf("%d%d%d",&n,&m,&q);

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

scanf("%d",&map[i][j]);

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

for (k=0;k<4;k++)

if (map[i][j]&&map[i+xx[k]][j+yy[k]])

num[i][j][k]=++tot;

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

for (k=0;k<4;k++)

if (num[i][j][k])

add(num[i][j][k],num[i+xx[k]][j+yy[k]][k^1],1);

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

for (k=0;k<4;k++)

for (x=0;x<4;x++)

if (x!=k&&num[i][j][k]&&num[i][j][x])

add(num[i][j][k],num[i][j][x],bfs(i+xx[k],j+yy[k],i+xx[x],j+yy[x],i,j));

while (q--)

{

scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);

printf("%d\n",spfa());

}

}

#1 lijie201602@2017-09-26 22:02:56
回复 删除
#include<cstdio>

const int oo=0x3f3f3f3f;

struct nod1{ int y,c,next; } a[40010];

struct nod2{ int x,y,t; } b[4000010];

int last[4010],list[4000010],num[35][35][5],h[4000],ma[35][35],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int m,n,q,tot,len=0,ex,ey,sx,sy,tx,ty;

bool v[35][35];

int min(int a,int b) { return a<b?a:b; }

void ins(int x,int y,int c) { len++; a[len].y=y; a[len].c=c; a[len].next=last[x]; last[x]=len; }

int bfs(int fx,int fy,int tx,int ty,int bx,int by)

{

if(fx==tx && fy==ty) return 0;

int x,y,z,head=1,tail=1,t;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) v[i][j]=false;

b[1].x=fx; b[1].y=fy; b[1].t=0; v[fx][fy]=true;

while(head<=tail)

{

x=b[head].x; y=b[head].y; t=b[head].t; head++;

for(int i=0;i<4;i++)

{

int xx=x+dx[i],yy=y+dy[i];

if(ma[xx][yy] && (xx!=bx || yy!=by) && v[xx][yy]==false)

{

if(xx==tx && yy==ty) return t+1;

tail++; b[tail].x=xx; b[tail].y=yy; b[tail].t=t+1; v[xx][yy]=true;

}

}

}

return oo;

}

int dfs()

{

if(sx==tx && sy==ty) return 0;

for(int i=1;i<=tot;i++) h[i]=oo;

for(int i=0;i<4;i++)

{

int xyi=num[sx][sy][i],xx=sx+dx[i],yy=sy+dy[i];

if(xyi)

{

h[xyi]=bfs(ex,ey,xx,yy,sx,sy);

list[i+1]=xyi;

}

}

int head=1,tail=4,ans=oo;

while(head<=tail)

{

int x=list[head++];

for(int i=last[x];i;i=a[i].next)

{

int y=a[i].y;

if(h[y]>h[x]+a[i].c)

{

h[y]=h[x]+a[i].c;

list[++tail]=y;

}

}

}

for(int i=0;i<4;i++)

{

int xyi=num[tx][ty][i];

if(xyi) ans=min(ans,h[xyi]);

}

if(ans==oo) return -1;

else return ans;

}

int main()

{

scanf("%d %d %d",&n,&m,&q);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) scanf("%d",&ma[i][j]);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=0;k<4;k++)

if(ma[i][j] && ma[i+dx[k]][j+dy[k]]) num[i][j][k]=++tot;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=0;k<4;k++)

if(num[i][j][k]) ins(num[i][j][k],num[i+dx[k]][j+dy[k]][k^1],1);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=0;k<4;k++)

for(int x=0;x<4;x++)

{

int ijk=num[i][j][k],ijx=num[i][j][x];

if(x!=k && ijk && ijx) ins(ijk,ijx,bfs(i+dx[k],j+dy[k],i+dx[x],j+dy[x],i,j));

}

while(q--)

{

scanf("%d %d %d %d %d %d",&ex,&ey,&sx,&sy,&tx,&ty);

printf("%d\n",dfs());

}

return 0;

}

查看更多回复
提交回复