为什么这份代码本机re,但是在洛谷ide上能跑
  • 板块学术版
  • 楼主sun_yh
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/8/8 17:46
  • 上次更新2023/11/6 20:55:43
查看原帖
为什么这份代码本机re,但是在洛谷ide上能跑
84129
sun_yh楼主2020/8/8 17:46

如题,虽然跑出来也错得离谱,先不考虑是否正确的问题

#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;
}
2020/8/8 17:46
加载中...