如题,虽然跑出来也错得离谱,先不考虑是否正确的问题
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,Q;
struct F{
int x,y,p;
}fro[100001],too[100001];
int len[100001];
int top,fir[31][31][4],nex[100001];
void add(F a,F b,int l){
//printf("%d\n",top);
top++;
fro[top]=a;
too[top]=b;
len[top]=l;
nex[top]=fir[a.x][a.y][a.p];
fir[a.x][a.y][a.p]=top;
return;
}
int wayx[4]={-1,0,1,0},wayy[4]={0,-1,0,1};
bool map[31][31];
int q1[31],q2[31],h1,t1,h2,t2,cnt[31][31];
int cost(int x1,int y1,int x2,int y2){
h1=h2=1,t1=t2=0;
q1[++t1]=x1,q2[++t2]=y1;
int uim=inf;
memset(cnt,0,sizeof cnt);
cnt[x1][y1]=1;
while(h1<=t1){
int x=q1[h1++],y=q2[h2++];
if(x==x2&&y==y2){
uim=cnt[x][y]-1;
break;
}
for(int i=0;i<=3;i++){
int x_=x+wayx[i],y_=y+wayy[i];
if(map[x_][y_]&&!cnt[x_][y_]){
q1[++t1]=x_;
q2[++t2]=y_;
cnt[x_][y_]=cnt[x][y]+1;
}
}
}
return uim;
}
F q[31];
int h,t,dis[31][31][4];
bool inq[31][31][4];
int spfa(F a,F b){
//printf("%d %d %d %d %d %d\n",a.x,a.y,a.p,b.x,b.y,b.p);
memset(dis,0x3f,sizeof dis);
memset(inq,0,sizeof inq);
h=t=1;
q[t]=a;
inq[a.x][a.y][a.p]=1;
dis[a.x][a.y][a.p]=0;
while(h<=t){
//printf("%d %d\n",h,t);
F now=q[h++];
for(int i=fir[now.x][now.y][now.p];i;i=nex[i]){//就是这里崩了,re
F to=too[i];
if(dis[now.x][now.y][now.p]+len[i]<dis[to.x][to.y][to.p]){
if(inq[to.x][to.y][to.p])
continue;
inq[to.x][to.y][to.p]=1;
dis[to.x][to.y][to.p]=dis[now.x][now.y][now.p]+len[i];
q[++t]=to;
}
}
}
return dis[b.x][b.y][b.p];
}
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",&map[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j]){
F now,to;
now.x=i,now.y=j;
for(int k=0;k<=3;k++){
now.p=k;
to.x=i+wayx[k],to.y=j+wayy[k],to.p=(k+2)%4;
if(map[to.x][to.y]){
printf("%d %d %d %d %d %d\n",now.x,now.y,now.p,to.x,to.y,to.p);
add(now,to,1);
}
else
continue;
to.x=i,to.y=j;
for(int l=0;l<=3;l++){
to.p=l;
if(to.p!=now.p&&map[i+wayx[l]][j+wayy[l]]){
map[i][j]=0;
printf("%d %d %d %d %d %d\n",now.x,now.y,now.p,to.x,to.y,to.p);
add(now,to,cost(i+wayx[k],j+wayy[k],i+wayx[l],j+wayy[l]));
map[i][j]=1;
}
}
}
}
while(Q--){
int x0,y0,x1,y1,x2,y2,ans=inf,ans_;
scanf("%d%d%d%d%d%d",&x0,&y0,&x1,&y1,&x2,&y2);
F now,to;
now.x=x1,now.y=y1;
to.x=x2,to.x=y2;
for(int i=0;i<=3;i++){
now.p=i;
for(int j=0;j<=3;j++){
to.p=j;
ans_=spfa(now,to);
map[x1][y1]=0;
ans_+=cost(x0,y0,x1+wayx[i],y1+wayy[i]);
map[x1][y1]=1;
ans=min(ans,ans_);
}
}
printf("%d\n",(ans>=inf)?-1:ans);
}
return 0;
}