AOJ 2425 A Holiday of Miss Brute Force

問題

変な六角座標上での最短路問題。移動にかかるコストが時間によって変わる。(座標, 時間, 無視した回数)を状態に持ってダイクストラ法で探索した。実装が面倒。

ソースコード

ll const inf = 1<<28;
double const pi = acos(-1);
 
int sx,sy,gx,gy;
int n;
int fx[1000], fy[1000];
int lx,ly;
int g[256][256];
inline int & ref(int arr[256][256], int x, int y){
    return arr[y+128][x+128];
}
 
inline int valid(int x,int y){
    return abs(x)<=lx && abs(y)<=ly;
}
 
struct state {
    int x,y,t, ign;
    bool operator<(const state& s)const{
        if(ign != s.ign) return ign>s.ign;
        return t>s.t;
    }
};
 
int d[6][256][256];
 
int solve(){
    priority_queue<state> q;
    rep(i,6)rep(j,256)rep(k,256)d[i][j][k]=inf;
    q.push({sx,sy,0,0});
    ref(d[0],sx,sy) = 0;
 
    while(q.size()){
        auto s=q.top();q.pop();
        int t=s.t, x=s.x, y=s.y, ign=s.ign;
        // printf("x:%d y:%d t:%d ign:%d\n",x,y,t,ign);
        if(ref(d[t%6], x, y) > ign) break;
        if(x==gx && y==gy) return ign;
        static const int dx[]={0, 1, 1, 0,-1,-1, 0};
        static const int dy1[]={1, 0,-1,-1,-1, 0, 0};
        static const int dy2[]={1, 1, 0,-1, 0, 1, 0};
 
        rep(i,7){
            int nx=x+dx[i];
            int ny=y+(x&1 ? dy2[i] : dy1[i]);
            int nign;
            if(i!=6 && i==abs(x*y*t)%6 && valid(nx,ny) && ref(g,nx,ny)!=1){
                nign=ign;
            } else {
                nign = ign+1;
                if(!valid(nx,ny) || ref(g,nx,ny)==1){
                    nx=x, ny=y;
                }
            }
 
            if(ref(d[(t+1)%6], nx, ny) > nign){
                // printf("(%d,%d) -> (%d,%d) t:%d ign:%d dir:%d\n",x,y,nx,ny,t,ign,i);
 
                ref(d[(t+1)%6], nx, ny) = nign;
                q.push({nx,ny,t+1, nign });
            }
        }
    }
    int ans=inf;
    rep(i,6)ans=min(ans,ref(d[i],gx,gy));
    if(ans==inf) ans=-1;
    return ans;
}
 
int main(){
    while(scanf("%d%d%d%d",&sx,&sy,&gx,&gy)!=EOF){
        scanf("%d",&n);
        memset(g,0,sizeof(g));
        rep(i,n){
            int x,y;scanf("%d%d",&x,&y);
            ref(g,x,y)=1;
        }
        scanf("%d%d",&lx,&ly);
        printf("%d\n",solve());
    }
}