aoj2425:A Holiday of Miss Brute Force

問題文

A Holiday of Miss Brute Force | Aizu Online Judge

解法

指示を無視した回数を距離と見立ててdijkstraをしたくなる。
(y,x,t)の三情報を状態として持てばうまくいくが、tの上限が大きくならないという保証がないので、おそらくまずい。
しかしよく考えると、tはmod 6での値を持てばいいとわかる。よってAC

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int dx[7]={0,1,1,0,-1,-1,0};
int dy[2][7]={{1,0,-1,-1,-1,0,0},{1,1,0,-1,0,1,0}};

int sx,sy,gx,gy;
bool ng[222][222];
int H,W;

const int INF=1001001001;
int dist[222][222][6];

bool ok(int y,int x){
    if(ng[y][x])return false;
    y-=100;x-=100;
    if(y<-H||y>H||x<-W||x>W)return false;
    return true;
}

signed main(){
    cin>>sx>>sy>>gx>>gy;
    sx+=100;sy+=100;gx+=100;gy+=100;
    int n;cin>>n;
    rep(i,n){
        int x,y;
        cin>>x>>y;
        x+=100;y+=100;
        ng[y][x]=true;
    }
    cin>>W>>H;

    fill_n(**dist,222*222*6,INF);
    dist[sy][sx][0]=0;
    priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>>que;
    que.push(make_tuple(0,sy,sx,0));
    while(que.size()){
        int c,y,x,t;
        tie(c,y,x,t)=que.top();
        que.pop();
        if(dist[y][x][t]<c)continue;

        int h=abs((x-100)*(y-100)*t)%6;

        rep(i,7){
            int ny=y+dy[x%2][i],nx=x+dx[i],nt=(t+1)%6;
            if(!ok(ny,nx))continue;
            if(dist[ny][nx][nt]<=c+(i!=h))continue;
            dist[ny][nx][nt]=c+(i!=h);
            que.push(make_tuple(c+(i!=h),ny,nx,nt));
        }
    }

    int mi=INF;
    rep(i,6)chmin(mi,dist[gy][gx][i]);
    if(mi==INF)cout<<-1<<endl;
    else cout<<mi<<endl;
    return 0;
}