AOJ 1334: Cubic Colonies

辺と辺の間をn等分 (n=1,2,...,7)した点を全部列挙してまたもや最短路。

ただ闇雲に重いだけ。(量だけなら1000の中ではかなり重いほうだと思う。)

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
char in[3][3][4];
int DIV=3;
int gcd(int a,int b){
	while(a){
		b%=a;int c=a;a=b;b=c;
	}return b;
}
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
	double x, y,z;
	Pt() {}
	Pt(double x, double y,double z) : x(x), y(y),z(z) {}
	Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y,z+a.z); }
	Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y,z-a.z); }
//	Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
	Pt operator-() const { return Pt(-x, -y,-z); }
	Pt operator*(const double &k) const { return Pt(x * k, y * k,z*k); }
	Pt operator/(const double &k) const { return Pt(x / k, y / k,z/k); }
	double ABS() const { return sqrt(x * x + y * y+z*z); }
	double abs2() const { return x * x + y * y+z*z; }
//	double arg() const { return atan2(y, x); }
	double dot(const Pt &a) const { return x * a.x + y * a.y+z*a.z; }
//	double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double ijk[110000];
int v[110000];
int can[4][4][4];
int canx[4][4][4];
int cany[4][4][4];
int canz[4][4][4];
int canxy[4][4][4];
int canyz[4][4][4];
int canzx[4][4][4];
int rev[110000];
char ss[4];
int main(){
	int a,b,c,d,e,f;
	while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f),a+b+c+d+e+f){
		for(int i=0;i<3;i++)for(int j=0;j<3;j++){
			scanf("%s",ss);
			for(int k=0;k<3;k++)in[k][j][i]=ss[k];
		}
		vector<Pt> hb;
		for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++){
			can[i][j][k]=canx[i][j][k]=cany[i][j][k]=canz[i][j][k]=0;
			canxy[i][j][k]=canyz[i][j][k]=canzx[i][j][k]=0;
		}
		for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++){
			if(i==0||i==3||j==0||j==3||k==0||k==3)can[i][j][k]=2;
			if(j==0||j==3||k==0||k==3)canx[i][j][k]=2;
			if(i==0||i==3||k==0||k==3)cany[i][j][k]=2;
			if(i==0||i==3||j==0||j==3)canz[i][j][k]=2;
			if(k==0||k==3)canxy[i][j][k]=2;
			if(i==0||i==3)canyz[i][j][k]=2;
			if(j==0||j==3)canzx[i][j][k]=2;
		}
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++){
			int key=0;
			if(in[i][j][k]=='#'){
				key=1;
			}else{
				key=2;
			}
			for(int l=0;l<8;l++){
				can[i+l/4][j+l%4/2][k+l%2]|=key;
			}
			for(int l=0;l<4;l++){
				canx[i][j+l/2][k+l%2]|=key;
				cany[i+l/2][j][k+l%2]|=key;
				canz[i+l/2][j+l%2][k]|=key;
			}
			for(int l=0;l<2;l++){
				canxy[i][j][k+l%2]|=key;
				canyz[i+l%2][j][k]|=key;
				canzx[i][j+l%2][k]|=key;
			}
		}
		/*for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				for(int k=0;k<4;k++)printf("%d ",can[k][j][i]);
				printf("\n");
			}
			printf("\n");
		}*/
		for(int i=0;i<=3;i++){
			for(int j=0;j<=3;j++){
				for(int k=0;k<=3;k++){
					if(can[i][j][k]==3)hb.push_back(Pt((double)i,(double)j,(double)k));
				}
				for(int k=0;k<3;k++){
					for(int l=2;l<=DIV;l++){
						for(int m=1;m<l;m++){
							if(gcd(m,l)!=1)continue;
							if(canz[i][j][k]==3)hb.push_back(Pt((double)i,(double)j,k+(double)m/l));
							if(cany[i][k][j]==3)hb.push_back(Pt((double)i,k+(double)m/l,(double)j));
							if(canx[k][i][j]==3)hb.push_back(Pt(k+(double)m/l,(double)i,(double)j));
						}
					}
				}
			}
		}
		int sz=hb.size();
		for(int i=0;i<sz;i++){
			v[i]=0;
			ijk[i]=99999999;
		}
		Pt start=Pt(a,b,c);
		Pt goal=Pt(d,e,f);
		for(int i=0;i<sz;i++){
			if((hb[i]-start).ABS()<EPS){
				ijk[i]=0;
			}
		}
		for(int i=0;i<sz;i++){
			int at=0;
			double dist=999999999;
			for(int j=0;j<sz;j++){
				if(!v[j]&&dist>ijk[j]){
					dist=ijk[j];at=j;
				}
			}
			v[at]=1;
		//	printf("%f %f %f: %f\n",hb[at].x,hb[at].y,hb[at].z,ijk[at]);
			if((hb[at]-goal).ABS()<EPS){
				printf("%.12f\n",dist);
				int cur=at;
				//while((hb[cur]-start).ABS()>EPS){
				//	cur=rev[cur];
				//	printf("%f %f %f: %f\n",hb[cur].x,hb[cur].y,hb[cur].z,ijk[cur]);
				//}
				break;
			}
			for(int j=0;j<sz;j++){
				if(v[j])continue;
				bool X=false;
				bool Y=false;
				bool Z=false;
				int xx=(int)(min(hb[j].x,hb[at].x)+EPS);
				int yy=(int)(min(hb[j].y,hb[at].y)+EPS);
				int zz=(int)(min(hb[j].z,hb[at].z)+EPS);
				if(ABS(hb[j].x-hb[at].x)<EPS&&ABS(hb[j].x-xx)<EPS)X=true;
				if(ABS(hb[j].y-hb[at].y)<EPS&&ABS(hb[j].y-yy)<EPS)Y=true;
				if(ABS(hb[j].z-hb[at].z)<EPS&&ABS(hb[j].z-zz)<EPS)Z=true;
				if(!X&&!Y&&!Z)continue;
				if(!X&&(int)(min(hb[j].x+1,hb[at].x+1)+EPS)!=(int)(max(hb[at].x+1,hb[j].x+1)-EPS))continue;
				if(!Y&&(int)(min(hb[j].y+1,hb[at].y+1)+EPS)!=(int)(max(hb[at].y+1,hb[j].y+1)-EPS))continue;
				if(!Z&&(int)(min(hb[j].z+1,hb[at].z+1)+EPS)!=(int)(max(hb[at].z+1,hb[j].z+1)-EPS))continue;
				bool can=false;
				bool Xs=false;
				bool Ys=false;
				bool Zs=false;
				if(ABS(hb[j].x-(int)(hb[j].x+EPS))<EPS)Xs=true;
				if(ABS(hb[j].y-(int)(hb[j].y+EPS))<EPS)Ys=true;
				if(ABS(hb[j].z-(int)(hb[j].z+EPS))<EPS)Zs=true;
				if(X&&canyz[xx][yy][zz]==3)can=true;
				if(Y&&canzx[xx][yy][zz]==3)can=true;
				if(Z&&canxy[xx][yy][zz]==3)can=true;
				if(X&&Y&&Xs&&Ys&&canz[xx][yy][zz]==3)can=true;
				if(Z&&Y&&Zs&&Ys&&canx[xx][yy][zz]==3)can=true;
				if(X&&Z&&Xs&&Zs&&cany[xx][yy][zz]==3)can=true;
				if(can){
					double tmp=(hb[j]-hb[at]).ABS();
					if(ijk[j]>tmp+ijk[at]){
						ijk[j]=tmp+ijk[at];
						rev[j]=at;
					}
				}
			}
		}
	}
}