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()); } }