这题我只想到60分解法了。。
正解还是好机智，要注意500个q其实都是在同一个图上面的【想想这个有什么用就好了ORZ。。
copy题解：
题解2：
结合起来就完全明白了ORZ。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 35
#define INF 0xfffffff int mymin(int x,int y) {return x<y?x:y;} int a[Maxn][Maxn];
int n,m,qs; int bx[]={,,-,},
by[]={-,,,}; queue<int > q;
int d[Maxn*Maxn*];
int bfs(int x,int y,int xx,int yy)
{
while(!q.empty()) q.pop();
memset(d,-,sizeof(d));
q.push((x-)*m+y);d[(x-)*m+y]=;
while(!q.empty())
{
int now=q.front(),nx,ny;
nx=now/m+;ny=now%m;if(ny==) ny=m,nx--;
if(nx==xx&&ny==yy) return d[now];
for(int i=;i<;i++) if(a[nx+bx[i]][ny+by[i]])
{
int nn=(nx+bx[i]-)*m+ny+by[i];
if(d[nn]==-)
{
d[nn]=d[now]+;
q.push(nn);
}
}
q.pop();
}
return -;
} int num[Maxn][Maxn][],cnt; struct node
{
int x,y,c,next;
}t[Maxn*Maxn*];int len;
int first[Maxn*Maxn*]; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} void init()
{
scanf("%d%d%d",&n,&m,&qs);
memset(a,,sizeof(a));
cnt=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) if(a[i][j])
for(int k=;k<;k++) if(a[i+bx[k]][j+by[k]])
{
num[i][j][k]=++cnt;
// printf("num_ %d %d %d = %d\n",i,j,k,num[i][j][k]);
}
len=;
memset(first,,sizeof(first));
int i,j;
for(i=;i<=n;i++) for(j=;j<=m;j++) if(a[i][j])
{
// printf("%d %d\n",i,j);
for(int k=;k<;k++) if(a[i+bx[k]][j+by[k]])
{
a[i][j]=;
for(int l=k+;l<;l++) if(a[i+bx[l]][j+by[l]])
{
int x=bfs(i+bx[k],j+by[k],i+bx[l],j+by[l]);
if(x==-) continue;
ins(num[i][j][k],num[i][j][l],x);
ins(num[i][j][l],num[i][j][k],x);
}
a[i][j]=;
ins(num[i][j][k],num[i+bx[k]][j+by[k]][-k],);
ins(num[i+bx[k]][j+by[k]][-k],num[i][j][k],);
}
}
/*for(int i=1;i<=len;i+=2)
{
printf("%d -> %d = %d\n",t[i].x,t[i].y,t[i].c);
}*/
} int ex,ey,sx,sy,tx,ty;
bool pp[Maxn*Maxn*],inq[Maxn*Maxn*];
int dis[Maxn*Maxn*]; int spfa(int st)
{
while(!q.empty()) q.pop();
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
q.push(st);dis[st]=;inq[st]=;
int ans=INF;
while(!q.empty())
{
int x=q.front();
if(!pp[x])
{
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y])
{
inq[y]=;
q.push(y);
}
}
}
}
else ans=mymin(ans,dis[x]);
q.pop();inq[x]=;
}
return ans;
} void ffind()
{
memset(pp,,sizeof(pp));
for(int i=;i<=qs;i++)
{
int ans=INF;
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(sx==tx&&sy==ty) printf("0\n");
else
{
for(int j=;j<;j++) pp[num[tx][ty][j]]=;
a[sx][sy]=;
for(int j=;j<;j++) if(a[sx+bx[j]][sy+by[j]])
{
int x=bfs(ex,ey,sx+bx[j],sy+by[j]);
// printf("%d %d %d = %d \n",sx,sy,j,x);
if(x==-) continue;
x+=spfa(num[sx][sy][j]);
// printf("%d %d %d = %d \n",sx,sy,j,x);
ans=mymin(ans,x);
}
a[sx][sy]=;
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
for(int j=;j<;j++) pp[num[tx][ty][j]]=;
} }
} int main()
{
init();
ffind();
return ;
}
注意一开始就在终点的特判【我被坑了ORZ....
放个数据，答案是377
2016-11-16 09:38:27